But there are problems with this. First, there are many possible TMs that could run such programs. We need to choose one - but such a choice contradicts the "inevitable" nature that Platonism is supposed to have.

The choice of your turing machine doesn't much matter, since all turing machines can simulate each other. If you choose the "wrong" turing machine, your measures will be off by at most a constant factor (the complexity penalty of an interpreter for the "right" machine language).