Lets roll in the science-mobile and discuss real, concrete things.
1. Not eating carbs has nothing to do with our hunter-gatherer origins, there are no over-arching truisms that can be made about the macronutrient distribution of how hunter-gatherers used to or currently eat. Concordantly, paleo "proper" insofar as it resembles utilizing our understanding of hunter-gatherer diets to eat healthier than a Standard American Diet is not necessarily low carb.
2. Eating carbs doesn't cause you to turn into the Stay-Puft man like magical fairy dust, even if they're relatively unhelpful to sedentary people as a nutritive calorie source. Sedentary people should get more protein and fat than carbs relative to what an athlete would.
Moving onto 'keto', which is the more GI/ketosis focused variety of low carb/paleo:
High-fiber and whole-grain calorie sources should be preferred to the opposite. The only thing that makes an apple not "junk food" is the fiber. Fiber has been shown to blunt the glycemic impact of carb-bearing foods. Apples are otherwise useless unless you really need the carbs to survive/fuel your activities.
>http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjourna...
>Determining which aspects of the Western lifestyle are truly aberrant for our species and pose the greatest risk of obesity is complicated by the conflicting and limited data on diet and metabolism in non-Western populations. For example, while Western diets are certainly more sugar-rich and energy-dense than more “traditional” diets and wild foods [4], [8], [9], many hunter-gatherers seasonally consume a large portion of their daily calories as honey [10], [11] (Fig. S2), which has high concentrations of glucose and fructose [12].
>As is typical among traditional-living Hadza, over 95% of their calories during this study came from wild foods, including tubers, berries, small- and large-game, baobab fruit, and honey [17] (Fig. S2).