People lose weight, temporarily, on all sorts of diets, restricted or not. It is the nature of specific diets that they tend to reduce appetite, and simply following a diet tends to reduce snacking - by virtue of selection bias, mostly (that is, people who are successfully following a diet are by definition people who aren't overeating).

Very traditional diets also tended to include lots of foods that are both highly processed and contain both sugars and fats, like cheese or sweet nut cakes. Paleo diets are a modern invention, and have little in common with the concept of what our ancestors ate. They often have deeply anachronistic ideas, like favoring raw foods, when the use of fire has been a core part of our ancestors consumption since way before Homo Sapiens existed.