Therefore, wouldn’t it be strange to rule out something using our current math/physics systems?

I get the thought, but math and physics are not the same. Math includes logic. When the authors of that paper make that argument, they don’t rely on our current understanding of physics. The theorems they use rely only logic. They are true independent of how the physics and the computation works.

Blackholes, neutron stars, quasars and other funny things that can’t be explained exactly DO exist after all

Yes, black holes inspired the paper. They do make the assumption, that a theory of quantum gravity would explain them. That’s what most people want out of such a theory.

How is it in any way narrow? The three theorems they use (Goedel, Tarski, Chaitin) are actually incredibly broad. They absolutely include things we can not even imagine.