The paradox of the stone is usually phrased as the question, "Can God create a rock so heavy He cannot lift it?" More expansively we could summarize it as the following dilemma (the particular form of which I borrow from C. Wade Savage):
(1) Either God can create a stone which He cannot lift, or He cannot create a stone which He cannot lift.
(2) If God can create a stone which He cannot lift, He is not omnipotent (because He cannot lift it).
(3) If God cannot create a stone which He cannot lift, He is not omnipotent (because He cannot create it).
(4) Therefore, God is not omnipotent.
It doesn't need to be a stone, of course. The paradox is more of a trivial curiosity than anything very profound; it relies on a notion of omnipotence as 'being able to do anything' and this is not the notion of omnipotence that was in view when traditional doctrines of omnipotence were developed, but simply one rather late offshoot, so (4) has to be suitably restricted.. And it is also often noted that the apparent force lies in the problematic assumption that among the things you must be able to do if you are able to do anything are logical impossibilities, which are not usually included in the scope of 'anything'.
What is not often recognized, though, is that even on its own terms the paradox of the stone is not actually a paradox, because there are no logical problems with answering 'Yes'. The problem is that (2), while it looks like it is similar to (3), can't be. The dilemma proposes a contrast between God's being able to cause Himself to be unable to do something, in which case we have an inability 'nested in' an ability, and God's being unable to cause Himself to be unable to do something, in which we have an 'unnested' inability. But in sophisticated positions (as opposed to mere crude simplifications) that do take omnipotence to be the ability to do anything (e.g., broadly Cartesian accounts of omnipotence), these will not function in the same way. For if we think of the ability to be able or unable (as one chooses), it always means that if you are unable to do something it is because of a logically prior ability. But these positions on omnipotence in these contexts are then essentially claims that there is an infinite series of such abilities: for any or ability inability you might name, God has the ability not to have that ability or inability, directly or indirectly, and that ability to have or lack the ability is logically prior. (And, indeed, broadly Cartesian accounts of omnipotence are sometimes explicit in one way or another about such an infinite series.) The modal operators for these abilities cannot collapse, so any claim of inability is relativized by its place in the infinite series; and thus saying that "God can create a stone He cannot lift" does not problematize the omnipotence in question because the inability is derivative: affirming means merely that God both can and cannot lift the stone, in different senses. He cannot lift it in the sense that He is exercising His ability not to be able to lift it; He could lift it simply by no longer exercising His ability not to be able to lift it.
We can find analogues in finite cases, of course. If I inject my legs with a chemical that produces indefinite paralysis, and I also have handy the antidote, can I or can't I walk to the store? 'Can' and 'Can't' depend on which abilities you have in view: the immediate ability of my legs to move or my ability with the antidote to make my legs movable. My overall abilities are branched, with a paralysis branch (in which I can't move my legs) and an antidote branch (in which I can). What the omnipotence case does is guarantee that for any 'paralysis' in the series there is an 'antidote' branch in the ability and that there can be no extrinsic impediment intervening; any 'paralysis' about the stone implies a previously available 'antidote' to the 'paralysis'. Thus the antecedent of (2) does not guarantee the consequent.
Such accounts of omnipotence are not at all the best accounts of omnipotence; but the paradox of the stone is not a particularly good reason for rejecting them. At least, it lacks the analytical sophistication to do much; you would needed a more logically advanced argument than stone paradoxes usually are to pin any actual logical problems on even the crude notion of omnipotence.