How to extent primitive recursion from natural numbers to finite strings? Primitive recursion seems to be related to bounded quantification. It is easier to make sense of bounded quantification with respect to natural numbers than to make sense of bounded quantification with respect to finite strings.


A relatively clean way out of this dilemma could be a two sorted language with both natural numbers and finite strings, and some basic functions between the two sorts, like the lengths of a string, or the string where one symbol is repeated n times.
A nicer solution could be to avoid the need for natural numbers, and work with some more native finite string related concepts, like head/tail, substring, ... instead. 


I wonder whether there exist a robust computational model (on finite strings) corresponding to primitive recursion, just like Turing machines represents a robust computational model (on finite strings) corresponding to general ($\mu$-) recursion.
You don't really need to do anything. Without loss of generality, let $\Sigma = \{0, \dots, d-1\}$.  A string in&nbsp;$\Sigma^*$ is (almost) just a natural number written in base-$d$. The only problem is that leading zeroes are significant in strings but not natural numbers so we instead associate the string $w_1\dots w_k\in\Sigma^k$ with the base-$d$ natural number that's written $1w_1\dots w_k$. The length function is just a suitably rounded logarithm, which is primitive-recursive anyway.

(The first way you'd try to compute a base-$d$ logarithm would probably be to use a while loop to repeatedly divide by&nbsp;$d$. But you can replace that with a for loop, since we know that $\log_d n\leq n$.)