I'm all for falsification, but this presupposes a hard definition of "paleo" that doesn't exist. Any interesting experiment would need to look at a more specific dietary hypothesis.

Even among particular subcategories of Paleo (Cordain, Harris, Wolf, etc.) there are a great many free variables. It's hard for something so vague to be easily falsified.

That said, perhaps one might attempt to undermine various assumptions that are common to the paleo community. If science were to somehow prove that refined grains positively (or even neutrally) impact human health, for instance, then you might consider "paleo" in general falsified.

Alternatively, one might go after the broad tenants of specific of paleo "schools". The Cordain or Wolf version of Paleo might be undermined by evidence that full-fat dairy is of near-uniform benefit (hard in itself. what is a "benefit"). Yet this would little effect the distinct hypotheses of Harris or Guyenet.

Loose Paleo is easy to poke holes in...

Things like omega6 balance, fructose, lectins etc are all arguable(and argued often) But an Organic, Natural, Whole Foods diet, eating food that ate what it's supposed to eat, is hard to contest. Evolution is difficult to disprove.

Most of the counter arguments become n=1, were all different and will react even slightly different to macro intake, specific foods etc based on environment and genetics. Arguing against one thing for one person is again easy, but for most, paleo is about toxin reduction, who can argue against that?

Various flavors of Paleo can easily generate falsifiable hypotheses; the focus on wheat, for example, suggests plenty of experiments.

The part that's hard to argue against is the fundamental paleo axiom of "don't eat what you didn't evolve to eat". To falsify that, you'd have to show that humans should eat what we didn't evolve to eat while avoiding what we evolved to eat. Who would expect that to be true? I mean virtually by definition, if you can eat it without health problems, you evolved to eat it. The trick is figuring out where that line is, where the health problems start, and even that's so highly individual as to render most generalized testing moot.

The thing that could falsify paleo for me is if someone could demonstrate that:

1. Human adaptation to food is actually orders of magnitude faster than I currently understand (say on the order of centuries rather than tens of millennia)
2. Selection pressure has been strong on humans even with civilization.

I tend to think that evolution is quite slow and even slower when you bring in societies that look out for the welfare of their citizens regardless of their fitness (which I'm not arguing against). It is, as you say, a bit intellectually dishonest to say there is no possible counter argument. Dairy is a perfect example of a food that some people might have adapted to just fine.

The concern I have about the argument that it must be good to eat like our ancestors is that for reasons having nothing to do with diet, our ancestors died at an early age. Hunter gatherers 50,000 years ago had a life expectancy of what, 25 years? My point is, they did not die of cardiovascular heart disease. They died of living in the elements, from animal attacks, from infections that are easily cured today, etc. So in general, we cannot conclude that our 70+ year lives are going to be healthiest if we eat like they did. For instance, maybe meat is bad for you because of the saturated fat, but this really only becomes a significant problem after 50 years of life.

I would say the problem with paleo is that taking out cheap grains, much of the world would be starving right now. As far as the intricacies of paleo, many people adapt quite well to a variety of whole foods diets. No one would argue that more broccoli is better than more twinkies, but would many of us here on this board do well eating like the Inuit, or Okinawans? Probably not, as we are somewhere in the middle. The same with the Masai. The beauty of paleo is that if we get rid of the psuedo-foods, much of the rest can truly come down to n=1 experimentation.