It does make sense that our ability to understand the incompleteness theorem is very close to self-contradictory -- I don't know that I'd say it is, without a doubt, self-contradictory; I have not dove deep into how provability logics might force □(a → (p ∧ ¬□p)) into a contradiction, and what you need for that (possibly with reasonable axioms it merely derives ¬□a which just means that if there is an algorithm for understanding then we'll never uncover it?).
QM does not by itself plug the hole in our understanding; Penrose has never said that to my knowledge. However a tiny part of quantum physics is the only known part of physics that's capable of producing nonalgorithmic results (the vast majority of QM is linear algebra in funny hats), hence if we've got a nonalgorithmic result it makes sense to follow our "best theories so far" towards that tiny part of quantum physics.