I claim that, if $g(x) \in k[[x]]$ is not a polynomial, then $g \circ c$ is a polynomial for at most $|F|^{k/2}$ polynomial $c$ of degree $\leq k$. We will always use the letter $c$ to represent a polynomial with $c(x)=0$.
Case 1: $g$ is transcendental over the field $k(x)$. In this case, I claim that $g \circ c$ is a polynomial only when $c$ is $0$. Proof: Suppose that $g(c(x)) = h(x)$ for some polynomial $h$. Then there is a polynomial relation $F(c(x), h(x))=0$ for some polynomial $f$. Set $G(x) := F(x, g(x))$. By hypothesis, $G \neq 0$, but $G(c(x))=0$. The only way this can happen is if $c=0$.
Case 2: $g$ is algebraic over $k(x)$. Let $F(x,g(x))=0$ be the minimal polynomial relation between $x$ and $g$. Let $A$ be the ring $k[x,y]/F(x,y)$. At this point I really, really want to use the language of algebraic geometry. If you aren't happy with this, I'll try to convert into commutative algebra, but it will be harder to write and, in my opinion, harder to read. My goal is the following claim:
Claim: If there is any nonzero $c$ such that $g \circ c$ is polynomial, then the ring $A$ is a subring of $k[u]$ for some $u \in \mathrm{Frac}(A)$.
Example: Let $g = (1+x)^{3/2}$. Then $F(x,y) = y^2 - (1+x)^3$. Letting $u = \frac{y}{1+x}$, we have $A \subseteq k[u]$, since $x=u^2-1$ and $y=u^3$.
Proof: $\mathrm{Spec}(A)$ is an algebraic curve. Since $F$ is the minimal polynomial relation, it is irreducible. Let $X$ be the normalization of $\mathrm{Spec}(A)$.
Let $h=g \circ c$. Now, $t \mapsto (c(t), h(t))$ is a map $\mathbb{A}^1 \to \mathrm{Spec}(A)$ and, since $c$ is nonconstant, is a nonconstant map. Since $\mathbb{A}^1$ is normal, this lifts to a nonconstant map $\mathbb{A}^1 \to X$. So $X$ has genus zero, and has at most one puncture. Since $X$ is affine, it has at least one puncture. So $X \cong \mathbb{A}^1$. In other words, the normalization of $A$ is $k[u]$, so we get an embedding $A \subseteq k[u]$ for some $u \in \mathrm{Frac}(A)$. $\square$
From now on, we will assume that there is some nonzero $c$ for which $g \circ c$ is polynomial. So we may assume that there is an embedding $A \subseteq k[u]$, with $\mathrm{Frac}(A) = k(u)$, and we fix such an embedding. Let $x = a(u)$ and $g(x) = b(u)$, for some polynomials $a$ and $b$. If $a$ has degree $1$, then $u$ is a linear function of $x$ and we can write $g$ as a polynomial in $x$, contradicting your hypothesis. So $\deg a \geq 2$. I claim that there are only $|F|^{k/\deg a}$ values of $c$ for which $g \circ c$ is a polynomial. Specifically, the polynomials $c$ of the form $a(\phi(t))$, where $\phi$ is a polynomial of degree $k/\deg a$.
Why is this? Well, if $c(t) = a(\phi(t))$, then $g(c(t)) = b(\phi(t))$ and is thus a polynomial. Conversely, if we have some $c$ such that $g \circ c$ is polynomial then, as discussed above, we get a map from the normalization of $A$ to $k[t]$. Take $\phi$ to be the image of $u$.
