Indeed he can! And the approach will not work. And he will then use said approach anyway. 
Wikipedia (yeah, I know) suggests the following definitions of omnipotence:
1.A deity is able to do anything that is logically possible for it to do.
2.A deity is able to do anything that it chooses to do.
3.A deity is able to do anything that is in accord with its own nature (thus, for instance, if it is a logical consequence of a deity’s nature that what it speaks is truth, then it is not able to lie).
4.Hold that it is part of a deity’s nature to be consistent and that it would be inconsistent for said deity to go against its own laws unless there was a reason to do so.[3]
5.A deity is able to do anything that corresponds with its omniscience and therefore with its worldplan
6.A deity is able to do absolutely anything, even the logically impossible.
So I guess it’s a case of “choose your flavor”. I’d personally go with [6] but the other 5 are reasonable interpretations.
The actual answer to the question from anyone on earth is, of course, “I don’t know”. People can suggest what they think the nature of an omnipotent god is, but nobody can know.
Of course God can solve a paradox. All he has to do is smite one of the dox, then there’s only one doc.
I’d reject #6 on the grounds that the logically impossible isn’t anything.
But that may depend on whether it’s possible in any sense whatsoever for the “laws” of logic to be different from what they are.
Chuck Norris can make a paradox solve itself while he makes love to its wife.
Plus you got this rock that can’t be moved, just cluttering up the place.
It does if we define ‘God’ as ‘nonsense that ceases to be nonsense’.
Only ih He is aware of the paradox in the first place. But then, it’s no longer paradox and, off we go…
On the subject of His existence, Godel took some time… Gödel's ontological proof - Wikipedia