Calculus is completely unnecessary here and so is Stirling's approximation. Let's do $c = 2$ as a warmup. How do we compare $2^n$ and $n!$? Well, observe that if $n \ge 2$ then
$$\begin{align*} n! &= 2 \times 3 \times 4 \times \dots \times n \\
&\ge 2 \times 2 \times \dots \cdot 2 \\
&\ge 2^{n-1}. \end{align*}$$
This gives that $2^n \le 2 \times n!$, so we can take $k_0 = 2, C_0 = 2$ in this case. Hopefully it is intuitively clear that this argument generalizes but let's do $c = 3$ just to be sure. How do we compare $3^n$ and $n!$? Well, if $n \ge 3$ then
$$\begin{align*} n! &= 2 \times 3 \times 4 \times \dots \times n \\
&\ge 2 \times 3 \times \dots \cdot 3 \\
&\ge 2 \times 3^{n-2}. \end{align*}$$
This gives that $3^n \le \frac{9}{2} n!$, so we can take $k_0 = 3, C_0 = \frac{9}{2}$ in this case.
The point is that, by definition, once $n$ goes past any given positive integer $m$, $n!$ is always increasing by at least a factor of $m$. So it always grows at least as fast as (a constant times) $m^n$ from that point on. This follows directly from the definition and nothing even slightly advanced is required, one should be able to "see" it. The generalization of the above argument to an arbitrary positive integer $m$ is that if $n \ge m$ then
$$\begin{align*} n! &= 2 \times 3 \times 4 \times \dots \times n \\
&\ge 2 \times 3 \times \dots (m-1) \times m \times m \times \dots \times m \\
&\ge m! m^{n-m} \end{align*}$$
which gives that $\boxed{ m^n \le \frac{m^m}{m!} n! }$. If we now set $m = \lceil c \rceil$ to be the smallest positive integer larger than $c$, then $c^n \le m^n$, so we can take $k_0 = m, C_0 = \frac{m^m}{m!} = \frac{\lceil c \rceil^{\lceil c \rceil}}{\lceil c \rceil!}$. Of course by increasing $k_0$ we can decrease $C_0$ arbitrarily but we don't need this.
