I recently came out against paleo in the open thread, and realized that I probably haven't yet heard the strongest arguments in favor of a paleo diet. So, what are said arguments?
EDIT: Or more generally, why should I eat less carbohydrates and more protein / fat?
Your grounds for skepticism match the heuristic that Anders Sandberg and Nick Bostrom propose in The wisdom of nature quite closely. They propose this heuristic to evaluate interventions to enhance humans, but it's clear that it has much broader applicability. Here's the relevant excerpt: