I wonder if sweet potatoes are just "tolerated" or actually encouraged in the Paleo Diet. While humans evolved eating tubers for perhaps 500.000 years, the actual tubers consumed should have been African varieties. Sweet potatoes originate from South America (current territories of Colombia and Venezuela) and most anthropologist date the human presence in South America to some 15.000 years. Anyway it is clear that humans did evolve out of Africa and therefore did not evolve eating sweet potatoes. On the other hand this vegetable is the main staple in the traditional diet of Okinawa, one of the most successful diets in terms of longevity.
Depends on your situation. If you have blood sugar issues, then steer clear. If you are trying to loss weight, keep intake to a minimum. If you are of good weight with healthy blood sugar control, IMO, they are fine. If you are of good weight with healthy blood sugar control and are very active with glycogen depleting exercises, or are trying to gain weight/muscle, or are trying to stop losing weight, some find they need to actively make an effort to eat lots of potatoes.
Potatoes are probably the most favored starch source in the paleo community for several reasons. One is that heavy tuber consumption is known to support several healthy tribal communities like the Kitavan. Another is because potatoes have a decent level of nutrition to them, unlike many other starch sources. The third is because, as you said, tuber consumption seems to have been prevalent as an ancient food source going way way back and so we are most likely well adapted to tuber consumption. And since sweet potatoes, unlike regular potatoes, are not a member of the nightshade family, they are safe for those who have problems with nightshade consumption.
While your point is correct that we may have eaten other tubers instead of sweet potatoes, since most of what we did eat back then, as far as all kinds of foods, is no longer available, most of the time we have to end up just looking at the biology, nutrition, science, and first hand experiences with each food in order to pick out likely biologically equivalent food sources to those we once ate. Plus the issue of regional variances is also going to make it unlikely that we can eat exactly as we once did. My ancestors came from Europe but I am living in America. Not only do I not know specifically what my ancestors once ate, but I am far from that land so even if I did know, I probably could not get it. So instead I endeavor to eat healthy biologically equivalent foods.
I don't think much of anything we evolved on is the same today, except maybe some wild game. All of our foodstuff has been domesticated and bred. So I think the only good heuristic is if it is plausibly biochemically similar. For instance, there was probably nothing remotely like a modern apple, but few argue that apples aren't paleo. (Kurt Harris and I might.) Kurt Harris makes a similar flavour of argument that butter is paleo: not by re-enactment, but by biochemistry. So my answer would depend on what kind of compounds are in it, especially defensive ones, and how much it differs from wild tubers, if it's possible to answer that.
crossposting: "Im thinking of getting off sweet potato due to its Neolithic status and trypsin inhibiters, its just not safe to eat raw... I mean I might as well start eating some grains if I thought potent anti-nutrients were acceptable?"