>> He points to a study on a skull from a Homo rhodesiensis man who lived 350 000 years ago. He was closely related to our ancestors in Africa, says the zoologist. The skull was found in Zambia in 1921, and his teeth were not in good condition. More precisely, they were pretty rotten ... He probably didn’t pick between his teeth to remove food debris. Another theory is that he ate a lot of honey.

Seems pretty relevant, after all! In fact, the thesis of the article seems to be that the agricultural revolution led to many more cavities, due to the increased availability of sugars. Indeed, the article suggests that the prevalence of cavities is tied with the availability of sugar to the population within a specific region.

If nothing else, dogs and cats get cavities and they're not eating a gallon of coke or a bucket of M&Ms...

Many fruits are quite sugary, and some people probably lived in areas where they could consume fruits regularly. Also, as another commenter stated, non-sugar carbohydrates can also pose risks.