There's a very underrated 'cave man' game like Snow Bros/Bubble Bobble that I quite like.
I think its called Caveman Ninja: Something, or Joe & Mac (I believe it was called different names in different countries)
However, note that there is a 'side scrolling platform game' version with this name/those characters, and then a 'single screen puzzle' style game like Bubble Bobble.
If I can find the exact name I'll let you know.