"Therein lies the rub. Do we really want a definition of "complexity of physical theories" that tells apart theories making the same predictions? "

Yes.

"Evolution by natural selection occurs" and "God made the world and everything in it, but did so in such a way as to make it look exactly as if evolution by natural selection occured" make the same predictions in all situations.

You can do perfectly good science with either hypothesis, but the latter postulates an extra entity - it's a less useful way of thinking about things precisely because it's more complex. It adds an extra cognitive load.

Selecting theories by their Kolmogrov complexity is just another way of saying we're using Occam's Razor. If you have two theories with the same explanatory power and making the same predictions, then you want to use the simpler one - not because it's more likely to be 'true', but because it allows you to think more clearly.