A counterexample to your claim: Ackermann(m,m) is a computable function, hence computable by a universal Turing machine. Yet it is designed to be not primitive recursive.
And indeed Kleene’s normal form theorem requires one application of the μ-Operator. Which introduces unbounded search.
Quoting https://en.wikipedia.org/wiki/Kleene%27s_T_predicate:
In other words: If someone gives you an encoding of a program, an encoding of its input and a trace of its run, you can check with a primitive recursive function whether you have been lied to.