The EMH is a description of how the market behaves when a sufficiently large number of independent actors are looking for alpha. It is not a prescription of how the market should behave.
The conclusion is that with a sufficiently large number of actors in the market all seeking profits by trying to find misevaluation of stock prices, the excess profits of any individual actor will (assuming they all have access to the same information) converge to zero.
Its less a paradox and more a matter of game theory. Every investment firm which gives up trying to look for alpha (believing it is fruitless) means the remaining firms have more opportunities to find stocks with available information not reflected in the price. There's no paradox here: each individual actor is incentivized to participate in order to not miss out on that potential for excess profits, and the net effect is the EMH.
If the market is efficient then there is no risk adjusted alpha, which renders the search for it a waste of time and effort, which means no actor would rationally continue it, which means there is no mechanism for price discovery, which would render the market totally inefficient.
This is the paradox.
EMH is unfalsifiable at best and tautological at worst.
Yeah, I think the "paradox" is usually a problem for pundits and academics and not practitioners. Lots of people have experience finding and correcting market inefficiencies, usually getting paid for it.