I used to live in China, so I've eaten some crazy stuff, and come to think of it most of the really weird shit qualifies unambiguously as paleo (aside from the vegetable oil it is often cooked in). So: bee larvae (in an omelette; delicious, tastes faintly of honey), large, stinging wasps (stir fried; very warming qi), deer penis soup (broth made from testicles), every kind of organ imaginable (most memorable: quartered pig brains in hot pot), whale (braised meat, cured blubber and raw meat with wonderful streaks of fat; in Japan; remarkably good, particularly the blubber), snake (with blood and bile served on the side) ... not sure what I'm forgetting ... silk worms ... I had the opportunity several times to eat scorpion and passed.
The only thing that I truly refuse to eat is dog, and my rationale for this rule was paleo before I knew what paleo was. I had a little speech I gave every time someone suggested that I eat it: dogs co-evolved with us, and as a species they are our friends and have helped us hunt since before the dawn of time, and so killing and eating a dog is equivalent to killing and eating a person. Although if my kid was starving I would no doubt think otherwise.
As to whether I would recommend eating weird stuff - why not? Eating shouldn't be boring, right?