It sounds like what you're talking about is computable structure theory, applied to categories in particular.
In computable structure theory, say we have a structure $\mathcal{S}$ consisting of a set $X$ together with some operations $f_i$, some constants $c_i$, and some relations $R_i$. (This signature is usually finite; if infinite, we usually demand that it be appropriately computable.) Then $\mathcal{S}$ is computably presentable if, well, it has a computable presentation: there is some isomorphic structure $\mathcal{A}\cong\mathcal{S}$ whose domain is a computable subset of $\omega$ and such that the relations and functions of the signature are each computable when restricted to the domain. (If the signature is infinite, we need a "uniformity" condition.) The bible of computable structure theory is the book by Ash and Knight: https://www.elsevier.com/books/computable-structures-and-the-hyperarithmetical-hierarchy/ash/978-0-444-50072-4
It turns out this has a bunch of different equivalent formulations. For example, we could demand that the domain be merely computably enumerable, or all of $\omega$; as long as $\mathcal{S}$ is infinite this would make no difference. Also, the graph of a function being c.e. is the same as the graph of a function being computable, so long as its domain is computable. So there's a lot of flexibility present. On the other hand, c.e.-ness versus computability is a serious issue for relations - see for example any of the papers:
which study computably enumerable partial orderings. But in your case, the way you're presenting categories is purely functional, so the subtleties don't come up.
Note that we can represent any structure by a transitive graph, in a suitably effective way; so computable category theory is already as broad as computable structure theory, full stop. So it's unclear what, specifically, categories will add to the equation, and in general there will be nothing nice which holds of categories which isn't just always true.
However, there's a couple neat dimensions that categories add to the situation, which interest me in particular. First, enrichment. I think there's a lot of interesting wiggle room to talk about what a "computable category enriched over topological spaces" (for example) ought to be. Actually, even pinning down what a "computable topological space" is is quite complicated - see e.g. http://www.jucs.org/jucs_15_6/elementary_computable_topology or http://ac.els-cdn.com/S016800720300054X/1-s2.0-S016800720300054X-main.pdf?_tid=3a1b6ed2-b316-11e4-b0e1-00000aacb35e&acdnat=1423787057_f06075c4a90fa6635a8c42f24e059e12 - so maybe a better place to start is something more algebraic like "computable category enriched over abelian groups." One immediate question right off the bat is how much uniformity we demand of the abelian-ness between different hom-sets; between "totally uniform" and "arbitrary," I think there's room for some interestingness.
Second, most interesting categories are uncountable, and everything I've described only makes sense for countable structures. There's a few ways to go, here (in general, the volume "Effective mathematics of the uncountable" is really interesting for this sort of thing). There are several versions of computability theory which make sense for uncountable objects, such as $\alpha$- or $E$-recursion; unfortunately, they often rely on the universe being appropriately well-orderable, or some similarly strong criterion. On the other hand, we can also look at what happens when we collapse a structure to be countable via forcing; see http://arxiv.org/abs/1405.7456. In many senses this is very well-behaved; on the other hand, for non-algebraic objects - e.g. topological spaces - this seems very destructive. So, figuring out the right perspective for computable uncountable categories could be very interesting.
