Dental wear patterns start changing around the advent of cereal agriculture. I suppose you could consider literally any cereal grain "processed junk" but that seems like an extreme categorization. This is just because of a massive increase in carbohydrate consumption, which vaguely strained the capacity of humans natural adaptations. But it seems like those humans having the energy to work eight hours a day is worth the trade off of having a toothache every now and then.
And moreover, cavemen did not have perfect teeth: not even close. They had *surprisingly good* teeth, when you consider they did not have modern dental hygiene (and the idea that they had *no* dental hygiene, and allowed the pure holiness of their paleo diet to cleanse the filth from their mouths, is incorrect. They had toothbrushes and toothpicks, pulled teeth, and cleaned cavities). They absolutely had cavities and tooth decay to a greater extent than modern humans with access to good dental hygiene. Most adults in the developed world have a whole set of bonus teeth we have to get surgically removed to replace teeth that we no longer lose to tooth decay. Most people consider losing even a *single* tooth to tooth decay to be a sign of poor dental hygiene
The myth of an enlightened, natural past contrasted with a degenerate, deviant future is a neurotic perception that kicks into overdrive around food: after all, the one thing we are not adapted to eat is poison, and our brain is the number one tool we use to navigate the world. If you are constantly paranoid you might be eating poison, you will probably eat less poison than your reporductive competition
It's no coincidence that most religions have some kind of moral proscriptions about diet: it's the same kind of thought pattern. However, you have the power to be a thinking person. You know what carbohydrates and fats do and how you use them, and what kinds of carbohydrates and fats and in what quantities produce what result. You don't have to designate food haram or halal to know if it's good for you, and don't have to rely on totemic categories like "processed" or "paleo" to tell you if it is.