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. 

<cite authors="Maietti, Maria Emilia">_Maietti, Maria Emilia_, [**Joyal’s arithmetic universe as list-arithmetic pretopos**](http://www.emis.de/journals/TAC/volumes/24/3/24-03abs.html), Theory Appl. Categ. 24, 39-83 (2010). [ZBL1245.03111](https://zbmath.org/?q=an:1245.03111).</cite>

However, for your particular question, I think an [arithmetic pretopos](https://ncatlab.org/nlab/show/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](https://ncatlab.org/nlab/show/natural+numbers+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](https://ncatlab.org/nlab/show/pretopos). The [image factorization](https://ncatlab.org/nlab/show/regular+category#factorization_properties), 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.