The Paleo diet insists we should only eat things our forefathers ate back in the stone age; our systems just aren't developed to process modern foods. It's an interesting idea that intuitively makes sense although the objection that it's crazy to get health advice from a group of people that had a life expectance of 32 is hard to overlook.
So you're mostly left with a diet of some vegetables and lots of animal protein from meat, fish and eggs. Especially grains are a big no-no. To the untrained eye it appears as yet another low-carb diet with a better back story. I think though that they are wrong about the grains.
I'm writing this while being on a trip to East-Africa, the cradle of humanity. And even though you don't see many primitive hominoids on the planes of the Serengeti, you do see baboons. Baboons aren't great apes so not very related to humans, but they do seem to fill a similar niche as early humans did; they're ape-like creatures living in social groups on the savannahs getting by on whatever they find.
This time of year the Serengeti looks like a field of grain. The rains make the grasses grow tall and all those grasses are laden with seeds. Those seeds are of course nowhere as big as modern grains but it is still free calories to the baboons. And so a common sight is to see a group of baboons "harvesting" "grains". It just seems very unlikely to me that our ancestors would just let that opportunity go.