Gödel's incompleteness theorems concern "formal axiomatic system containing basic arithmetic" to quote Wikipedia. POW is an algorithm not a formal axiomatic system so theorems do not apply.
According to the Curry-Howard correspondence, there is an isomorphism between programs (algortihms) and proofs.
So the Gödel's incompleteness discoveries should be extendable to algortihms.
Interesting necro
I guess Gödel's incompleteness theorem being applicable to algorithms is more or less reflected in the halting problem? Doesn't seem to be really relevant for PoW though. Both Gödel's incompleteness theorem and the halting problem require a minimum of complexity to be present which you don't have in Bitcoin's PoW algorithm (or even Bitcoin script).