Perhaps this will help build a bit of intuition. The theorem your citing is about regular points on manifolds and their preimages. The key here is that the theorem says nothing about how these preimages vary as the point moves smoothly on the manifold. With the kernel of a bundle map, ensuring that it is a submanifold involves showing that the sub spaces smoothly vary as we vary the point p. One can see that the only way we can get smoothness is by looking at the smooth structure of the base space of the target bundle. This is exactly what the theorem your citing is missing...smoothness in p
Let $p\in M$, let $f\in C^\infty\left(N\right)$, and let $X\in T_pM$. By assumption, $\left(F_*X\right)\left(f\right)=X\left(f\circ F\right)=0$. Let $\left(U,\varphi\right)$ be a smooth chart containing $p$. Then
$$X=\sum_iX^i\left.\frac{\partial}{\partial x^i}\right|_p=\sum_iX^i\left(\varphi^{-1}\right)_*\left.\frac{\partial}{\partial x^i}\right|_{\varphi\left(p\right)},$$
which implies that
$$\left(\sum_iX^i\left(\varphi^{-1}\right)_*\left.\frac{\partial}{\partial x^i}\right|_{\varphi\left(p\right)}\right)\left(f\circ F\right)=\sum_iX^i\left.\frac{\partial}{\partial x^i}\right|_{\varphi\left(p\right)}\left(f\circ F\circ\varphi^{-1}\right)=0,$$
which in turn, by basic calculus, implies that $F$ is constant on $U$, i.e., $F\left(x\right)=c$ for some $c\in N$ and every $x\in U$.
Since $M$ is connected, it is the case that $M$ is path connected. Let $q\in M$ and let $\gamma:\left[0,1\right]\to M$ be a path connecting $p$ and $q$. Since, as above, $F$ is constant on each smooth chart $\left(U_{\gamma\left(x\right)},\varphi_{\gamma\left(x\right)}\right)$ containing $\gamma\left(x\right)$ for every $x\in\left[0,1\right]$, it is the case that $F\equiv c$ on $M$ since $F\left(p\right)=c$ and $\gamma$ is continuous.
Best Answer
Note that for any connected topological space $M$ with open cover $\mathscr{U}$, any two points $a,b \in M$ there is a collections of open sets $\{U_1,\dots,U_n\ | U_i \in \mathscr{U} \}$ such that $a\in U_1$ only , $b \in U_n$ only, and $U_i \cap U_j \neq \emptyset$ for $|i-j|\leq 1$ (Willard's Topology).
By hypothesis, for any point $p \in M$ there are neighbourhood $U_p$ such that the rank of $F$ constant there. Take $\mathscr{U} = \{U_p : \forall p\in M\}$ as the open cover for $M$. By above theorem, for any point $a,b \in M$, there are $\{U_1,\dots U_n\ : U_i \in \mathscr{U}\}$ such that $a \in U_1$, $b \in U_n$ and $U_i \cap U_j \neq \emptyset$ for $|i-j|\leq 1$. Lets say that the rank of $F$ at $U_1$ is $r$. For any $p \in U_1 \cap U_2$, rank $F$ at $p$ is $r$, hence rank $F$ on $U_2$ is $r$. Do this inductively we have rank $F$ on $U_n \ni b$ is $r$. Since $a,b \in M$ arbitrary then rank $F$ constant on $M$.