It seems to me that either human-level GI is impossible or it is not. But, we humans constitute an existence proof that it is not impossible.

Of course. This is why I'm not saying human-level GI is impossible. I'm saying that designing it from scratch is impossible.

And, Gödel's incompleteness theorems really have nothing to do with how hard it might be to come up with a solution to a computable problem.

My argument is not in any sense a proof from Goedel incompleteness. Goedel incompleteness is just a suggestive analogy.

...there are various NP-hard optimization problems for which good approximate solutions can be found in polynomial time. Since human or super-human AGI does not require a maximally intelligent program, even if you could show that the AGI optimization problem is NP-hard that would say nothing about the difficulty of finding a human or super-human level AGI.

I mostly agree: except for the "nothing" part. I think it would definitely cause me to update towards "designing AGI is infeasible". I hinted at a possible relation between intelligence and LK-complexity. If such a relation can be proven and human intelligence can be estimated we would have a more definite answer.