Would our ancestors have caught birds and eaten them? Of course, probably on a regular basis.
We can look at them today and say they are high in something we have technically decided is bad for us at this time (and may be decided is actually good for us at another time). People like to believe we have absolute knowledge on what is good/bad at this time. Of course we don't. We look back at people 30 years, 60 years, 100 years etc ago and think they knew nothing. Humans will discover new nutrients, new effects different foods have on the body. I am pretty sure humans have been eating fowl for as long as meat so I would definitely give it a pass.
Would we have for a long time been gathering huge amounts of nuts, grinding them and then cooking them? Hmmm no (especially since a lot of nuts ie almonds are naturally poisonous)
Dairy - questionable. We have been drinking it for many generations and consume something similar as babies. Probably best to leave out but the high fats ones may be fine.
Chocolate and coffee surprise me. Caffeine without a doubt affects the nervous system and rest of the body. It's definitely not natural. Is it bad? Maybe not but I doubt it's good to be taking a drug every day. I think people justify it due to their addictions. I mean really it's bitter tasting, not something naturally likeable (I don't think any kid tastes plain coffee for the first time and goes wow that's good!). I do drink coffee but try not to, I get jittery and crash from it too, but caffeine is addictive.
What surprises me the most is insistence on high amounts of veggies. I agree with Kurt Harris (came to the same conclusion before reading his beliefs), that although they might not do any harm and can add variety to a diet, they are not essential.
Compare the primary reasons for avoiding grains:
Toxic plant defenses? Check
Only been eating for a short period in our history? Check
High in starch? (Some but not most, and many people think starch is fine now)
Of course there is no proof that we haven't been eating plants forever(same as grains), but follow the logic. Pretty much all modern veggies have only been bred for maybe 5-10000 years (at most). Their ancestors didn't taste too good, were smaller, and toxic. So wild veggies tasted bad and offered little caloric return. Drop yourself in an wilderness area anywhere in the world. You're not surviving on veggies (if you can even find any that taste decent), you need to find meat to live (or bugs, wild tubers may keep you alive for a bit). Our ancestors simply wouldn't have wasted time trying to eat veggies unless they were starving. Will I still eat them for variety? Yes. But I think the Paleo community is still trying to fit into the mold of old 'healthy eating' styles by putting more veggies in the diet than necessary.