I'm not sure if this is what you want, but it is not difficult to prove that if f and g are primitive recursive functions, then the set A = { (x,y) | f(x) = g(y) } is a primitive recursive subset of the natural number plane. That is, the characteristic function of this set is primitive recursive. The (trivial) reason is that the characteristic function is simply the composition of the characteristic function of equality with f and g.

One can therefore have primitive recursive access to that set when defining other primitive recursive functions, such as the ones you will need in your commutative diagram.

As you and Reid have observed, when this set is empty, then there can be no pull back in the category of primitive recursive functions. But when it is nonempty, then we can define primitive recursive functions r, s on N^{2} to make the commutative square, by mapping r(x,y) = f(x) and s(x,y) = g(y), when (x,y) is in A, and otherwise r(x,y) = a and s(x,y) = b for some fixed (a,b) in A. This makes the square commute, and it has the universal property for pullbacks, because if r' and s' from N to N make the square commute (fr' = gs'), then we can define t:N to N^{2} by t(n) = (r'(n),s'(n)). By commutativity, this is inside A, and the whole diagram commutes.