I have no reason to believe that stevia increases the risk of cancer, but I'm afraid that arguing it is likely to be safe because it "coevolved" with humans is basically falling into the naturalistic fallacy with extra steps.
For stevia to be arguably safer due coevolution with humans, the following would need to be true:
1. There is a selective pressure for stevia to not increase the risk of cancer in humans.
2. There is a selective pressure on humans to not have an increased risk of cancer from consuming stevia.
In other words, it is firstly to argue that a stevia plant which had a tendency to increase cancer risk in humans would be significantly less likely to reproduce. This effect would be hard enough even if the hypothetical carcinogen were to be otherwise selectively neutral, but it could have a selectively positive pressure if it were an essential hormone or defence against insects, pathogens, competitors, etc.
Secondly, it is to argue that if stevia were potentially carcinogenic, then humans that were susceptible to its effects were significantly less likely to reproduce. This fails on two levels. First, consider that even in the cut-and-dried cause of cancer that is smoking, lung cancer is still extremely rare among young smokers. Lung cancer patients are virtually always well past their reproductive age, meaning that even if a genetic mutation to be immune to tobacco were to appear (or indeed it may well already exist) then said mutation still has no selective advantage with regards to the consumption of tobacco. Second, even if a hypothetically-carcinogenic stevia[0] could exert selective pressure on humans to become unaffected by it, then that effect would only have taken place on the populations which consumed significant amounts of stevia over generations and not humanity as a whole.
[0] Which I insist, I don't believe is the case.