Every example of a total, computable but non-primitive recursive function seems to be explicitly constructed for proof theory, or in Godelian proofs of "what is the name of this book?" kind. But is there a non-primitive recursive function or algorithm that occurs naturally, like in physics or number theory or even in industry software?
This answer gives us a hint, namely that an interpreter for a language more powerful than primitive recursion, is itself not primitive recursive. For example, System F has no self-interpreter, and thus any interpreter for System F is not self-recursive.