You have a name conflict in US english, as some sweet poatoes are
called yams. But there is a big family of *real* yams, which are not
at all related to sweet potatoes other than that they are also tubers.
There is evidence that (real) yam was eaten in west Africa 30000 years ago,
so it can really be considered "paleo" I think.
- Hans