I think your understanding of the incompleteness theorem is a little, well, incomplete. The proof of the theorem does involve, essentially, figuring out how to write down "this statement is not provable" and using liar-paradox-type-reasoning to show that it is neither provable nor disprovable.
But the incompleteness theorem itself is not the liar paradox. Rather, it shows that any (consistent) system rich enough to express arithmetic cannot prove or disprove all statements. There are things in the gaps. Gödel's proof gives one example ("this statement is not provable") but there are others of very different flavors. The standard one is consistency (e.g. Peano arithemtic alone cannot prove the consistency of Peano arithmetic, you need more, like much stronger induction; ZFC cannot prove the consistency of ZFC, you need more, like a large cardinal).
And this very much does come up for real systems, in the following way. If we could prove or disprove each statement in PA, then we could also solve the halting problem! For the same reason there's no general way to tell whether each statement of PA has a proof, there's no general way to tell whether each program will halt on a given input.
It set off the flamewar detector. I've turned that off now.
Anyway, I’m not really sure where Penrose is going with this. As a summary, incompleteness theorem is basically a mathematical reformulation of the paradox of the liar - let’s state this here for simplicity as “This statement is a lie” which is a bit easier than talking about “ All Cretans are liars”, which is the way I first heard it.
So what’s the truth value of “This statement is a lie”? It doesn’t have one. If it’s false, then it’s true. But if it’s true, then it must be false. The reason for this paradox is that it’s a self-referential statement: it refers to its own truth value in the construction of its own truth value, so it never actually gets constructed in the first place.
You can formulate the same sort of idea mathematically using sets, which is what Gödel did.
Now, the thing about this is that as far as I am aware (and I’m open to be corrected on this) this never actually happens in reality in any physical system. It seems to be an artefact of symbolic representation. We can construct a series of symbols that reference themselves in this way, but not an actual system. This is much the same way as I can write “5 + 5 = 11” but it doesn’t actually mean anything physically.
The closest thing we might get to would be something that oscillates between two states.
We also ourselves, don’t have a good answer to this problem as phrased. What is the truth value of “This statement is a lie”? I have to say “I don’t know” or “there isn’t one” which is a bit like cheating. Am I incapable of consciousness as a result? And if I am indeed conscious instead because I can make such a statement instead of simply ”True” or “False”, well I’m sure that an AI can be made to do likewise.
So I really don’t think this has anything to do with intelligence, or consciousness, or any limits on AI.