I wonder if there are some hard core paleo purist in terms of eating only those foods that were available (in almost identical form) some 10 thousand years ago. I will start with fish, seafood: it has not changed, so that would make it. Also meats from any wild animal would be pure-paleo. On the other hand basically all mammals that were domesticated have undergone great changes and great human selection so cows, pigs, or goats would be out of the question. Of course milk and dairy would be non-pure-paleo, and most vegetables and fruits too, since they have been extensively selected and modified through thousands of years of neolithic agriculture. And potatoes, sweet potatoes, cocoa or tomatoes are also non pure-paleo, because they have South American origin (humankind, we are told, did not originate in the Americas). Again I am not at all saying that we embrace this ultra-strict rules and restrict our food sources so much, just wondering whether you are aware of anyone suggesting this pure-paleo view! Now if there are indeed some "pure paleo" followers what do they say that we should eat?
Actually most fish would be off the menu as well. Folks weren't going out and catching tuna or flounder or sea bass or cod or netting big hauls of sardines. The Inuit, for example, focus their hunting on marine mammals--big targets. Trying to catch fast swimming schooling fish or bottom dwelling ocean fish in a canoe or kayak isn't terribly easy, feasible, or worth the effort relative to trying to harpoon a seal or nailing salmon swimming upstream or picking off a trout in a stream. So seafood would consist of whatever mollusks and crustaceans are easy pickings on the shoreline, marine mammals (which you can't legally eat except for the Inuit), and probably whatever fish you can get in rivers and streams. Or, if you're lucky enough to live near a reef, you can probably swim out to the reef and nail some fish that way. But in a lot of places, going out to sea would have been a bad idea compared to foraging in tide pools or camping out near salmon spawning grounds. Here in Southern California, for example, you'd have to contend with the cold water, strong currents, rocky shores, and a healthy population of Great Whites. I'd probably do what the natives here did, namely, kill myself a dear, get a bunch of acorns and call it a day.
still, i reckon that the difference between a 'paleo' cow and a modern (even CAFO) one is much less than the difference between a wild 'paleo' apple and a highly palatable one (aka 'fruit candy') you can find in a modern supermarket
We've got toxins now that have been detected even in the most remote spots. And beyond that, I don't think we can ever quite know for sure how things were back then, there may be factors no one has thought to consider. I think we should put more energy into figuring out how things stand today and how food is actually interacting with our bodies rather than speculating overmuch about the unknowable past.
Neanderthin is the "sharp stick on the savannah plain" book and he describes a pretty pure form of Paleo. Hard to get a copy, ut there's an old website at neanderthin.com the author, Ray Audette, had RA and diabetes when he started researching nutrition.