Since the set of critical points is always closed, it suffices to assume that $\phi$ (or, more generally, its restriction to the set of its critical points) is proper. (A map is called {\it proper} if the pre-image of every compact set is compact.)
One can formulate various sufficient conditions in terms of $M$. For example
$M$ is compact;
$M$ is a graph of a function $f:\mathbb R^m\to\mathbb R^{k-m}$ such that $\sup \|df\|<1$;
$M$ is a closed submanifold and its curvatures decay fast enough, e.g., all principal curvatures with respect to any normal at a point $x\in M$ are bounded above by $c|x|^{-1}$ for some constant $c<0$.
I doubt there is a nice "if and only if condition".
UPDATE. As for your you second question (about examples), you may be a confused by terminology here. The term "closed manifold" usually means "compact and having no boundary". In this case, the set of focal points is indeed closed because the normal exponential map is proper. However, "closed submanifold" can also mean "a submanifold which is a closed subset of the ambient space" (this is what I meant above, although "properly embedded submanifold" would be a less confusing term). With this meaning, the set of focal points is not necessarily closed and can even be dense.
For example, let $\{p_i\}_{i\in\mathbb N}$ be an enumeration of all rational points in the plane. Choose a sequence $\{R_i\}$ of positive reals that goes to infinity sufficiently fast. Construct a curve $\gamma:(-\infty,\infty)\to\mathbb R^2$ such that, for every $i$, $\gamma$ contains an arc of the circle of radius $R_i$ centered at $p_i$. This can be done so that $\gamma$ has no self-intersections and $|\gamma(t)|\to\infty$ as $t\to\pm\infty$. Then the image of $\gamma$ is a properly embedded one-dimensional submanifold of $\mathbb R^2$ and all $p_i$'s are its focal points.