I don't really see any reason why it couldn't be Turing complete, as long as it was completely deterministic (no "rand()" etc) and the specification included a maximum number of operations (which Bitcoin's Script already does)
What am I missing? Is the idea that without loops the transaction size can be used to estimate the computation required without actually performing it, and thus the appropriately sized transaction fee required?
Nakamoto designed script to be non-Turing complete from the very beginning (it was mentioned in his white paper). I suspect it was for security reasons. You don't want arbitrary complex code running on miners machine. At the very least, it could obstruct the system.
Script is not mentioned at all in the Bitcoin white paper. Perhaps you are thinking of a comment he made elsewhere.
Bear in mind that in the Bitcoin design it's not just miners who have to run scripts, it's all nodes, yet fees accrue only to the miners. Bitcoin does use fees to try and make computationally expensive transactions financially expensive as well, but that's just a basic antiflood mechanism, the fees don't actually get collected by those doing the work.
What am I missing? Is the idea that without loops the transaction size can be used to estimate the computation required without actually performing it, and thus the appropriately sized transaction fee required?