I'm going with Peacemaker. I don't remember if it can be acquired later, but that would fit the 'paradox' and 'high' parts since it has an ironic name and is found in a tower overlooking Kalm.
Yes! Right on. Here's the logic for all the lines.

High over the earth, (As BG-57 said, it's found in Kalm's Tower)
The paradox sleeps, (BG got it again, this is a reference to the ironic name of the weapon)
North of rebirth, (Kalm is almost directly north of Fort Condor)
And south of the deeps. (And directly south of a large patch of ocean.)

Bows to the marksman, (This stanza, while being key to the specifics, is also probably the most obscure. The marksman refers to the Sniper CR, the next best weapon after the Peacemaker. It's also meant to clue people in to the fact that the riddle has something to do with Vincent)
Though it masters the first. (Peacemaker is the weapon you get after Quicksilver, Vincent's initial equipment)
Bequeaths the best, (Highest growth)
In exchange for the worst. (Fewest materia slots)

When you find it again, (This alludes to the fact that it's an item that can be obtained more than once)
Need it you'll not, (This is sort of supposed to lead up to the fact that it won't be useful, because you'll have gotten things that are better than it)
After the ultimate price, (Aeris' death)
A negligible cost. (It's something that can be purchased)


Congratulations, and my sincerest thanks, BG ^___^ I'm very glad that you got it.