Descartes gives us at least two different ways around this paradox. The first comes straight out of Catholic dogma.
By Christian reasoning (and Hindu, for that matter), God did become finite (in the latter case, over and over again), he just remained omnipotent at the same time in a different form. God in the form of the Creator (or Vishnu) could easily make a rock that God in the form of Jesus (or Krishna) could not lift.
By the magical logic of trinitarianism (or alternately by the non-dual interpretation of what an avatar really is), employing this notion, Descartes both multiplies and does not infringe the unity of God. That cannot make sense to humans, but by dogma, that is our problem, not God's. So there is no logic in insisting that by God, you did not mean his incarnations or avatars, because there is no distinction, even though the distinction is clear and obvious to us, the difference we insist upon is just an artifact of human limitation, not an aspect of reality.
The second way around the paradox comes from more directly considering the nature of omnipotence. An omnipotent being, by Descartes logic, could create square circles, but those would have to exist in a way humans could not comprehend them; unless he also changed humans... If God can do everything, real or unreal, conceivable or inconceivable, possible or impossible, the paradox goes away. You just end up with lots of copies of God and worlds full of absolute nonsense (at least from a human point of view) in a Meinongian, modal-realist sort of way.
Descartes' real point is that not only is God the being that creates stuff, he is also the being that creates rules, including rules about possibilities. And he is free to change them, or to create exceptions. This is the principle of miracles, and miracles are pretty much the point of having a God who intercedes.
The God who makes up both the stuff and the rules has no problem at all with your paradox. God can clearly make up a rock that occupies the whole of space. That rock, of course, cannot be moved. The inability to move it is not about power, it is implicit in the definition of space (and of the whole thereof). But Descartes' God is also free to simply add a dimension to space, so he can move the rock. And he could then expand his rock to be four-dimensional and fill that space, which he could then move in a new fifth dimension. An infinite regress, but not a paradox.