Asymptotic formulas might be asking for a lot, but there is some work by I. Barany et al. See:
RANDOM POINTS AND LATTICE POINTS IN CONVEX BODIES
IMRE BA ́RA ́NY (in BAMS 2008) and the paper referred to therein by Balog/Barany:
Balog, Antal(H-AOS); Bárány, Imre(H-AOS)
On the convex hull of the integer points in a disc. Discrete and computational geometry (New Brunswick, NJ, 1989/1990), 39–44,
DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 6, Amer. Math. Soc., Providence, RI, 1991.
11H06 (11P21 52C07)
The former talks about some nice probabilistic results, the latter shows that there is an estimate of the form $c_1r^{2/3} \leq N(r) \leq c_2 r^{2/3},$ where $N(r) = C_n,$ and $r=n$ in your notation.
EDIT Answering my own question in the comments: it is a result of Renyi-Sulanke, 1963, that for $n$ random points in the disk, the expected number of extremal points is $O(n^{1/3}),$ so this is of the same order as for lattice points. A bit surprising.
I spent some time working this problem and discovered the following generalization. There's no new information here about the $2^{x-1}+5$ problem, so this is not much of an answer to that specifically. But we can say some similar things about some similar functions.
Let $F(x)$ be a composition of functions $x$, $c$, $c^\square$, $\square + \square$, $\square \cdot \square$, and $\square!$. For example, we might have $F(x) = 2^{6^x + x^2} + (x !)^2 + 3^x \cdot x - 3$, but not $F(x) = x^x$. Let $F^k(x)$ denote the $k^\text{th}$ iterate of $F$, so for example $F^2(x) = F(F(x))$.
Lemma: $F^k(x) ~\text{mod}~ m$ is eventually periodic in $k$.
Proof: First re-write $F(x)$ so that all the bases are factored into primes, for example $F(x) = 2^{6^x} = 2^{2^x \cdot 3^x}$. Now with $m = p^a \cdot b$ and $(p,b) = 1$, define $g_p(m) = \text{ord}_b(p)$, and observe that $p^{a+x} \equiv p^{(a + x) ~\text{mod}~ g_p(m)} ~\text{mod}~ m$. Assume as an inductive hypothesis that $F^k(x) ~\text{mod}~ n$ is eventually periodic in $k$ for all $1 \leq n < m$. By taking all the exponents $\text{mod}$ an appropriate composition of $g$ functions we get a function $G$ such that for sufficiently large $x$, $F(x) \equiv G(x) ~\text{mod}~ m$ — for example, if $F(x) = 2^{3^x+x}+x^7$, consider $G(x) = 2^{3^{x ~\text{mod}~ g_3(g_2(m))} + x ~\text{mod}~ g_2(m)} + x^7$ — then for sufficiently large $k$ we have $F^{k+1}(x) \equiv G(F^k(x)) ~\text{mod}~ m$ and combined with the inductive hypothesis and $g_p(m) < m$ this implies $F^k(x) ~\text{mod}~ m$ is an eventually periodic function of $k$.
Factorials are allowed too since they are eventually equal to $0 ~\text{mod}~ m$ and we can remove them from the expression, but I'm not sure how to handle general $\square^\square$ power compositions or primorials.
$\square$
Corollary: If $x$ never occurs outside of an exponent in the expression defining $F(x)$, like $F(x) = 2^{x-1} + 5$ and $F(x) = 2^{7^x+x}\cdot 5^x +3$, but not like $F(x) = 2^x + x$ or $F(x) = 2^x \cdot x$, call it restricted. Then $F^k(x) ~\text{mod}~ m$ is eventually fixed (periodic with period $1$) for all $m$ if and only if $F$ is restricted. However, this doesn't really explain why it should be that $F^k(x) ~\vert~ F^{k+1}(x)$ as requested. It's simply a generalization of the observations in Update #1, but it applies to a much wider class of functions than I originally suspected.
Corollary: For all $x, m \in \mathbb{N}$, there exists a $q \in \mathbb{Q}$ such that for all $k \in \mathbb{N}$, $F^k(x) \equiv \lfloor q \cdot m^k \rfloor ~\text{mod}~ m$. If $F$ is restricted then $q$ has a denominator of the form $m^z \cdot (m-1)$.
An idea I have is to compute some of these rationals for various $F, m, x$ and find cases with the same $m$ and two different functions $F$ and $G$ where the corresponding rationals have some of the same base-$m$ digits at the same positions. Since it is impossible to evaluate iterates of $F$ and $G$ beyond small arguments, if there is no obvious reason for this relationship, then determining for exactly which $k$ is it the case that $m ~\vert~ F^k(x) - G^k(y)$ may turn out to be a good puzzle problem requiring essentially the argument above plus calculations.
Best Answer
For $n\geq 7$, Erdős proved in 1932 that there is a prime $n/2<p\leq n$ of the form $p=4k+3$. From this he deduces (in the same paper) that $1!$, $2!$, $6!$ are the only factorials which can be written as a sum of two squares.