It is true that no organism is ever "perfectly" adapted to its environment, but again a more useful analysis would quantify the degree of adaptation. This could be done in lots of different ways -- some measure of the size of the local neighborhood of "gene space" that has been searched, say -- and then we could have a proper conversation about how the degree of adaptation is affected by population size or the rate of environmental change.
Let's take the specific case of the paleo diet. (Which for the record, I don't follow.) There is no question that humans have had diet-relevant mutations since the paleo era, such as lactose tolerance in some Europeans. The question is: have we had enough follow-up mutations? The first mutation, which lets adults get calories from cow's milk, has a huge selective advantage so it spreads rapidly. However, the subsequent mutations, which (say) reduce bloating, or reduce the risk of breast cancer, etc. don't have as big an advantage so they don't spread as rapidly and you are thus unlikely to have them even if you are lactose tolerant. Some of what I'm calling follow-up mutations might not even exist yet, but would in the normal course of another million years of human evolution. Given that you are very probably not currently desperate for calories, you might very well make the sensible decision not to drink milk but instead eat something your body does have a good set of follow-up mutations for, such as vegetables or nuts.
TL;DR: Despite a lot of name calling ("fantasy", "nostalgia"), nothing in this article gives any real reason to question the hypothesis that humans have been at times past better adapted to their environment than they are now.