But we couldn't. In general, SETI couldn't even detect such a civilization even if it was in the star system closest to earth:
> If an extraterrestrial civilization has a SETI project similar to our own, could they detect signals from Earth?
> In general, no. Most earthly transmissions are too weak to be found by equipment similar to ours at the distance of even the nearest star. But there are some important exceptions. High-powered radars and the Arecibo broadcast of 1974 (which lasted for only three minutes) could be detected at distances of tens to hundreds of light-years with a setup similar to our best SETI experiments.
The OP is right, in order for their to be a paradox we have to assume that civilizations much more advanced than ours are using a particular type of tech (the kind we're looking for, like radio broadcasts), that their using much stronger signals that we have ever used, and that the time period they used these hypothetical super powerful radio signals happens to be at the right time for us to encounter them. IE, let's say they used them for 2,000 years before moving on to other tech, but the signals only reached earth between 1,548,000-1,546,000 BC, or 450,000-458,000 BC, etc.
People are making a set of very, very specific assumptions based on little evidence. Then they see that the evidence that is available suggests that it's unlikely that every single one of their assumptions is correct, and they respond by calling it a paradox.