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.