The paleo diet is all about the hypothesis that we are not well adapted
to the diet we eat today (and some of us have eaten more or less for
up to 10,000 years), and are better adapted to one that we may have 
eaten for the million or so years before.

Well, but what if humans underwent some major metabolic changes in the
last 100,000 years, as we became "modern" humans?  Maybe those metabolic
changes improved reproductive success but hurt our overall health, 
especially under the dietary constraints of a hunter gatherer society?
Maybe we developed agriculture because those changed humans /needed/
a different food?

One such change might be a much longer childhood.  Chimpanzees grow 
and mature much faster than humans... even if you adjust for their
overall life expectancy.   Well, some scientist had argued that 
there was evidence that until quite recently, genus Homo grew and
matured at a rate much more like Chimpanzees than we do today.  If
this were the case, such a big change in the rate of growth surely
would have serious metabolic implications?

Maybe, but here's an article that says that this wasn't the case.
At least 160,000 years ago we already grew at the same slow pace
as today.

http://www.scienceblog.com/cms/ancient-fossil-shows-growth-profile-similar-to-modern-man-12783.html

:j