Here are some off-the cuff ideas.

First, as I think Saal's answer starts to hint at, there's no particular reason to restrict attention to $(n,n)$-categories. It seems more natural to think about $(n+k,n)$-categories for various values of $n,k$.

To fix ideas, let's start with $n=1$. A $(1+k,1)$-category is a 1-category whose hom-spaces are all $k$-truncated. Let $Spaces_k$ denote the $\infty$-category of $k$-truncated spaces. Also, let's not worry about Rezk completeness for the moment.

We know that the simplex category $\Delta$ is dense (in the $Spaces$-enriched sense) in $(\infty,1)$-categories. So it's also dense in $(1+k,1)$-categories. But it's reasonable to guess that in the $Spaces_k$-enriched sense, there is a subcategory of $\Delta_{\leq [K]} \subset \Delta$ with $K+1$-many objects, which is already dense in $Cat_{(k+1,1)}$. But what is $K(k)$? When $k=1$, we can take $K = 2$. I *suspect* that in general we can take $K = k+1$. This would be in line with the way people often treat stacks via truncated simplicial objects, with the truncation level depending on how truncated the stacks are. At any rate, finding such a $K(k)$ is something which should be readily computable -- if I feel less lazy later I might try to work it through here.

Now, $\Delta_{\leq [K]}$ is finite as a $(1,1)$-category. But as an $(\infty,1)$-category, this is not so clear. Nevertheless, its nerve has only finitely many nondegenerate simplices in each degree. Since we're mapping only into $Spaces_k$, we only need to go up to the $k+1$-simplices of its nerve.

So we see that $Cat_{(k+1,1)}$ should be model-able in terms of presheaves valued in $Spaces_k$ on the finite simplicial set $sk^{k+1}\Delta_{\leq K}$ (where I think that $K = k+1$). The Segal conditions are not additional coherence diagrams, but just conditions that certain maps are isomorphisms.

The number of coherence diagrams in this model is the number of $\leq k+1$-simplices in the nerve of $\Delta_{\leq k+1}$. This is the number of strings of $k$ composable morphisms in the category. We can cut down the model slightly by restricting to the 1-object subcategory on $[k+1]$ itself, since everything else is a retract of that object and so the category of presheaves is the same. The number of nondegenerate $l$-simplices is $|Hom_\Delta([k+1],[k+1])|^{l-1}$. I think that $|Hom_\Delta([a],[b])|$ may be related to Stirling numbers? At any rate, we get an upper bound of $(k+1)^{(l-1)(k+1)}$. Adding these up from $l=0$ to $l=k+1$, we get an upper bound of something like $(k+1)^{(k+1)^2}$.

To do something similar for higher values of $n$, you could work with analogous full subcategories of Joyal's category $\Theta$, for instance.

Anyway, those estimates are pretty rough. But I wouldn't be surprised if it's not *too* much bigger than what a "sharp" upper bound would give you!