For any manifold $M$ (dropping the Riemannian structure) there exists no such constant $k(M)$. In fact, there exists a smooth function which cannot be approximated by functions in $\operatorname{Morse}_k(M)$ for all $k \in \mathbb{N}$. An explicit counterexample can be constructed based on ideas similar to the previous answer. We make use of the following simple fact.
Lemma. Let $X$ be a topological space and $f \in \mathrm{C}_{\rm c}(X)$ be nonnegative. If $g \in \mathrm{C}_{\rm c}(X)$ satisfies $\|f - g\|_{\mathrm{C}^0} < \tfrac{1}{2} \|f\|_\mathrm{C^0}$, then the maximum of $g$ is attained in the interior of $\operatorname{supp} f$. $\square$
Let $b_0 \in \mathrm{C}^{\infty}_{\rm c}(\mathbb{R})$ be a nonnegative bump function supported on $[1, 2]$, such as the one defined by
$$
b_0(x) =
\begin{cases}
\exp\left(\frac{1}{(1-x)(2-x)}\right) &\text{if } x \in [1,2] \\
0 &\text{otherwise}
\end{cases}\,.
$$
Now pick a sequence $\{a_i\}_{i\in\mathbb{N}}$ which satisfies $a_0 = 1$ and
$$2^ia_i < \min_{j < i} \frac{1}{2^{j i} \big\| b_0^{(j)}\big\|_{\mathrm{C}^{0}}}$$
for $i > 0$, and define $b_i \in \mathrm{C}^{\infty}_{\rm c}(\mathbb{R})$ by $b_i(x) = a_i b(2^i x)$. It follows that the sum $b = \sum b_i$ is smooth and supported on $[0, 2]$. Finally, let $\phi \colon U \to \mathbb{R}^{n}$ be a chart and define $f \in \mathrm{C}^{\infty}(M)$ by
$$
f(x) =
\begin{cases}
b(\phi_1(x)) \cdots b(\phi_n(x)) &\text{if } x \in U \\
0 &\text{otherwise}
\end{cases}\,.
$$
Suppose, for the sake of contradiction, that there exists a sequence of functions $\{f_i\}_{i=0}^{\infty}$ in $\operatorname{Morse}_k(M)$ which converges to $f$ in the $\mathrm{C}^2$ topology. Being finer than the $\mathrm{C}^0$ topology, there will exist some integer $j$ such that
$$
\| f_j - f \|_{\mathrm{C}^0} < \tfrac{1}{2} \min_{i \leq k} \| b_i \|^n,
$$
which implies $f_j$ attains a maximum in the interior of $\phi^{-1} \big((\operatorname{supp} b_i)^n\big)$ for all $i \leq k$. In particular, this implies $f_j$ has at least $k+1$ critical points, which is a contradiction.