To me that is not a paradox, just logical, with very low incidence you just find much more false positives than real positives. What is paradoxical about that?

It's why we don't screen for just any condition in the general population. I.e. we just do it for 65+ y/o's, 3 packs/day smokers because there we may actually find it worth the cost of the program.

There's no contradiction anywhere in this scenario, just people's incorrect intuitions meeting (mathematical) reality.