Did Wheeler really believe that physics was undecidable?
The inference "the universe would be completely computable, so no undecidable/uncomputable things could exist" is invalid.

In the effective topos, where everything is computable, there are many undecidable phenomena. For example, all real numbers are computable, but equality of real numbers is undecidable (and computable).

To give you an idea how this happens: equality of reals is a map $\mathbb{R} \times \mathbb{R} \to \Sigma$ which is implemented by a Turing machine that takes (Turing machines that compute) reals $x$ and $y$ and returns a non-boolean truth value represented by a Turing machine which terminates if, and only if, $x \neq y$.

In contrast, equality of natural numbers is decidable. It is a map $\mathbb{N} \times \mathbb{N} \to \{0,1\}$ which takes two natural numbers and outputs either $0$ or $1$, depending on whether they are equal.

As far as physcists are concerned, I would be careful about learning computability theory from them. I wouldn't want anyone to learn physics from me.