The seminal event for increasing per-capita sugar intake was the introduction of Coca Cola/soda.
If you aren't familiar with the tragedy of sugar on traditional Native Americans, introduction of processed American foods has created an epidemic on reservation.
"Type II Diabetes, the Modern Epidemic of American Indians"
Christopher McDougall's book "Natural Born Heroes" is about the heroes of Crete during WW2 who were able to fight off the Germans by putting up extraordinary resistance by doing, among other things, hiking for miles and miles over treacherous territory for 20 hours straight. It makes an argument that a paleo-based diet is the reason why they were able to do it. With this diet, they were able to run and evade for long distances without fatigue. Meats and other proteins provide a sustainable, longer-lasting source of energy in contrast to the spike of sugar.
Generally you are correct and protein shouldn’t spike insulin like sugar, but certainly some protein will spike insulin. For example I’ve been experimenting with various proteins in ketosis and even whey isolate spikes my insulin and knocks me out of ketosis.
Maybe they weren’t doing paleo diets so much as high fat diets and entering ketosis where the body stops using glucose/glucogon as primary source of energy and begins using ketones for cellular energy.
I weighed ~113kg at the end of high-school (c. 2005) and the first step I took towards losing weight was switching out regular soda for diet variants. People say 'diet' is still bad, but switching definitely cut down on my caloric intake. Slowly, but surely, I started paying more attention to caloric intake...which brings me to where I am, now.