A more directed answer are Joyal's arithmetic universes. For a while it was once quite difficult to find a description of these, but Maria Maietti has proposed an official description.

Maietti, Maria Emilia, Joyal’s arithmetic universe as list-arithmetic pretopos, Theory Appl. Categ. 24, 39-83 (2010). ZBL1245.03111.

However, for your particular question, I think an arithmetic pretopos suffices. The basic idea is as follows.

First, if $\boldsymbol{1} \xrightarrow{o} \mathbf{N} \xleftarrow{\sigma} \mathbf{N}$ is parameterized natural number object in a a category $\mathcal{A}$ with finite products and disjoint coproducts, then all the $k$-ary primitive recursive functions $f$ are representable in $\mathcal{A}$ in the sense that there is a morphism $\mathbf{N}^k \xrightarrow{\phi} \mathbf{N}$ such that $$\require{AMScd}\begin{CD} \boldsymbol{1} @>(\sigma^{n_1}o,\ldots,\sigma^{n_k}o)>> \mathbf{N}^k \\ @| & @VV{\phi}V \\ \boldsymbol{1} @>>{\sigma^{f(n_1,\ldots,n_k)}o}> \mathbf{N} \end{CD}$$ commutes for all $n_1,\ldots,n_k$. In fact, we can build such a category where all the arrows $\mathbb{N}^k \to \mathbb{N}$ represent primitive recursive functions and nothing more.

Since not all computable functions are primitive recursive, this is not sufficient. To get all computable functions, we need to add unbounded search and then close under composition. That is, given a $k+1$-ary primitive recursive $f$ such that $$(\forall n_1,\ldots,n_k)(\exists m)[f(n_1,\ldots,n_k,m) = 0]$$ the function $$g(n_1,\ldots,n_k) = \min\{m : f(n_1,\ldots,n_k,m) = 0$$ is computable.

On the categorical side, this can be achieved by requiring the category to be a pretopos. The image factorization, which comes with pretoposes being regular categories, allows one to prove that the category is closed under unbounded search in the internal sense. Namely, if $G \hookrightarrow \mathbf{N}^k \times \mathbf{N}$ is a subobject such that $G \hookrightarrow \mathbf{N}^k \times \mathbf{N} \to \mathbf{N}^k$ is regular epi, then $G$ is isomorphic the graph of a morphism $\mathbf{N}^k \xrightarrow{\gamma} \mathbf{N}$. One recovers unbounded search by taking $G \hookrightarrow \mathbf{N}^k\times\mathbf{N}$ to be the pullback of $\mathbf{N}^k \times \mathbf{N} \xrightarrow{\phi} \mathbf{N}$ along $\boldsymbol{1} \xrightarrow{o} \mathbf{N},$ where $\phi$ represents the primitive recursive function $f$ as described above.

A more directed answer are Joyal's arithmetic universes. It was once quite difficult to find a description of these, but Maria Maietti has proposed an official description.

Maietti, Maria Emilia, Joyal’s arithmetic universe as list-arithmetic pretopos, Theory Appl. Categ. 24, 39-83 (2010). ZBL1245.03111.

However, for your particular question, I think an arithmetic pretopos suffices. The basic idea is as follows.

First, if $\boldsymbol{1} \xrightarrow{o} \mathbf{N} \xleftarrow{\sigma} \mathbf{N}$ is parameterized natural number object in a a category $\mathcal{A}$ with finite products and disjoint coproducts, then all the $k$-ary primitive recursive functions $f$ are representable in $\mathcal{A}$ in the sense that there is a morphism $\mathbf{N}^k \xrightarrow{\phi} \mathbf{N}$ such that $$\require{AMScd}\begin{CD} \boldsymbol{1} @>(\sigma^{n_1}o,\ldots,\sigma^{n_k}o)>> \mathbf{N}^k \\ @| & @VV{\phi}V \\ \boldsymbol{1} @>>{\sigma^{f(n_1,\ldots,n_k)}o}> \mathbf{N} \end{CD}$$ commutes for all $n_1,\ldots,n_k$. In fact, we can build such a category where all the arrows $\mathbb{N}^k \to \mathbb{N}$ represent primitive recursive functions and nothing more.

Since not all computable functions are primitive recursive, this is not sufficient. To get all computable functions, we need to add unbounded search and then close under composition. That is, given a $k+1$-ary primitive recursive $f$ such that $$(\forall n_1,\ldots,n_k)(\exists m)[f(n_1,\ldots,n_k,m) = 0]$$ the function $$g(n_1,\ldots,n_k) = \min\{m : f(n_1,\ldots,n_k,m) = 0\}$$ is computable.

On the categorical side, this can be achieved by requiring the category to be a pretopos. The image factorization, which comes with pretoposes being regular categories, allows one to prove that the category is closed under unbounded search in the internal sense. Namely, if $G \hookrightarrow \mathbf{N}^k \times \mathbf{N}$ is a subobject such that $G \hookrightarrow \mathbf{N}^k \times \mathbf{N} \to \mathbf{N}^k$ is monic and regular epi, then $G$ is isomorphic the graph of a morphism $\mathbf{N}^k \xrightarrow{\gamma} \mathbf{N}$. One recovers unbounded search by taking $G \hookrightarrow \mathbf{N}^k\times\mathbf{N}$ to be the pullback of $\mathbf{N}^k \times \mathbf{N} \xrightarrow{\phi} \mathbf{N}$ along $\boldsymbol{1} \xrightarrow{o} \mathbf{N},$ where $\phi$ represents the primitive recursive function $$\hat{f}(n_1,\ldots,n_k,m) = \begin{cases} 0 & \text{if $f(n_1,\ldots,n_k,m) = 0$ and $\prod_{i=0}^{m-1} f(n_1,\ldots,n_k,i) \neq 0$,} \\ 1 & \text{otherwise.} \end{cases}$$

A more directed answer are Joyal's arithmetic universes. For a while it was once quite difficult to find a description of these, but Maria Maietti has proposed an official description.

Maietti, Maria Emilia, Joyal’s arithmetic universe as list-arithmetic pretopos, Theory Appl. Categ. 24, 39-83 (2010). ZBL1245.03111.

However, for your particular question, I think an arithmetic pretopos suffices. The basic idea is as follows.

First, if $\boldsymbol{1} \xrightarrow{o} \mathbf{N} \xleftarrow{\sigma} \mathbf{N}$ is parameterized natural number object in a a category $\mathcal{A}$ with finite products and disjoint coproducts, then all the $k$-ary primitive recursive functions $f$ are representable in $\mathcal{A}$ in the sense that there is a morphism $\mathbf{N}^k \xrightarrow{\phi} \mathbf{N}$ such that $$\require{AMScd}\begin{CD} \boldsymbol{1} @>(\sigma^{n_1}o,\ldots,\sigma^{n_k}o)>> \mathbf{N} \\ @| & @VV{\phi}V \\ \boldsymbol{1} @>>{\sigma^{f(n_1,\ldots,n_k)}o}> \mathbf{N} \end{CD}$$ commutes for all $n_1,\ldots,n_k$. In fact, we can build such a category where all the arrows $\mathbb{N}^k \to \mathbb{N}$ represent primitive recursive functions and nothing more.

Since not all computable functions are primitive recursive, this is not sufficient. To get all computable functions, we need to add unbounded search and then close under composition. That is, given a $k+1$-ary primitive recursive $f$ such that $$(\forall n_1,\ldots,n_k)(\exists m)[f(n_1,\ldots,n_k,m) = 0]$$ the function $$g(n_1,\ldots,n_k) = \min\{m : f(n_1,\ldots,n_k,m) = 0$$ is computable.

On the categorical side, this can be achieved by requiring the category to be a pretopos. The image factorization, which comes with pretoposes being regular categories, allows one to prove that the category is closed under unbounded search in the internal sense. Namely, if $G \hookrightarrow \mathbf{N}^k \times \mathbf{N}$ is a subobject such that $G \hookrightarrow \mathbf{N}^k \times \mathbf{N} \to \mathbf{N}^k$ is regular epi, then $G$ is isomorphic the graph of a morphism $\mathbf{N}^k \xrightarrow{\gamma} \mathbf{N}$. One recovers unbounded search by taking $G \hookrightarrow \mathbf{N}^k\times\mathbf{N}$ to be the pullback of $\mathbf{N}^k \times \mathbf{N} \xrightarrow{\phi} \mathbf{N}$ along $\boldsymbol{1} \xrightarrow{o} \mathbf{N},$ where $\phi$ represents the primitive recursive function $f$ as described above.

A more directed answer are Joyal's arithmetic universes. For a while it was once quite difficult to find a description of these, but Maria Maietti has proposed an official description.

Maietti, Maria Emilia, Joyal’s arithmetic universe as list-arithmetic pretopos, Theory Appl. Categ. 24, 39-83 (2010). ZBL1245.03111.

However, for your particular question, I think an arithmetic pretopos suffices. The basic idea is as follows.

First, if $\boldsymbol{1} \xrightarrow{o} \mathbf{N} \xleftarrow{\sigma} \mathbf{N}$ is parameterized natural number object in a a category $\mathcal{A}$ with finite products and disjoint coproducts, then all the $k$-ary primitive recursive functions $f$ are representable in $\mathcal{A}$ in the sense that there is a morphism $\mathbf{N}^k \xrightarrow{\phi} \mathbf{N}$ such that $$\require{AMScd}\begin{CD} \boldsymbol{1} @>(\sigma^{n_1}o,\ldots,\sigma^{n_k}o)>> \mathbf{N}^k \\ @| & @VV{\phi}V \\ \boldsymbol{1} @>>{\sigma^{f(n_1,\ldots,n_k)}o}> \mathbf{N} \end{CD}$$ commutes for all $n_1,\ldots,n_k$. In fact, we can build such a category where all the arrows $\mathbb{N}^k \to \mathbb{N}$ represent primitive recursive functions and nothing more.

Since not all computable functions are primitive recursive, this is not sufficient. To get all computable functions, we need to add unbounded search and then close under composition. That is, given a $k+1$-ary primitive recursive $f$ such that $$(\forall n_1,\ldots,n_k)(\exists m)[f(n_1,\ldots,n_k,m) = 0]$$ the function $$g(n_1,\ldots,n_k) = \min\{m : f(n_1,\ldots,n_k,m) = 0$$ is computable.

On the categorical side, this can be achieved by requiring the category to be a pretopos. The image factorization, which comes with pretoposes being regular categories, allows one to prove that the category is closed under unbounded search in the internal sense. Namely, if $G \hookrightarrow \mathbf{N}^k \times \mathbf{N}$ is a subobject such that $G \hookrightarrow \mathbf{N}^k \times \mathbf{N} \to \mathbf{N}^k$ is regular epi, then $G$ is isomorphic the graph of a morphism $\mathbf{N}^k \xrightarrow{\gamma} \mathbf{N}$. One recovers unbounded search by taking $G \hookrightarrow \mathbf{N}^k\times\mathbf{N}$ to be the pullback of $\mathbf{N}^k \times \mathbf{N} \xrightarrow{\phi} \mathbf{N}$ along $\boldsymbol{1} \xrightarrow{o} \mathbf{N},$ where $\phi$ represents the primitive recursive function $f$ as described above.