Okay, I should have thought a bit more about this question before posting it on MathOverflow: the answer is No, for a combination of rather straightforward reasons. Moreover, the answer is No even for a locally finite connected graded coalgebra over a field $k$, where "locally finite" means that every graded component is finite-dimensional. For the sake of completeness (and to avoid this), here is how to construct a counterexample:
§1. Let $C$ be a coalgebra. Let $f\in\overline{C^{\ast}}^{2}$ be arbitrary. Then, the rank of $f$ will mean the smallest $m\in \mathbb{N}$ such that $f$ can be written in the form $f=\sum\limits_{i=1} ^{m}\lambda_{i}g_{i}h_{i}$ with $\lambda_{i}\in k$, $g_{i}\in\overline {C^{\ast}}$ and $h_{i}\in\overline{C^{\ast}}$.
§2. Let $k=\mathbb{R}$. Let $n\in\mathbb{N}$ be positive. Let $T$ denote the graded $k$-bialgebra $k\left[ X_{1},X_{2},...,X_{n}\right] $ which, as a $k$-algebra, is the polynomial ring $k\left[ X_{1},X_{2},...,X_{n}\right] $, and whose coalgebra structure is given by $\Delta\left( X_{i}\right) =X_{i}\otimes1+1\otimes X_{i}$ and $\varepsilon\left( X_{i}\right) =0$ for all $i$. This is clearly a locally finite connected graded $k$-bialgebra.
Let $f_{n}:T\rightarrow k$ be the $k$-linear map which sends every polynomial to the sum of its coefficients before $X_{i}X_{j}$ over all $1\leq i < j\leq n$. Then, this map $f_{n}$ lies in $\overline{T^{\ast}}^{2}$ and has rank $n-1$.
Proof. The element $f_{n}$ of $T^{\ast}$ can be written as $f_{n} =\sum\limits_{1\leq i < j\leq n}\xi_{i}\xi_{j}$, where $\xi_{\ell}:T\rightarrow k$ is the $k$-linear map which sends every polynomial to its coefficient before $X_{\ell}$.
From $f_{n}=\sum\limits_{1\leq i < j\leq n}\xi_{i}\xi_{j}=\sum\limits_{i=1} ^{n-1}\underbrace{\xi_{i}}_{\in\overline{T^{\ast}}}\underbrace{\left( \xi_{i+1}+\xi_{i+2}+...+\xi_{n}\right) }_{\in\overline{T^{\ast}}}$, it is clear that $f_{n}$ lies in $\overline{T^{\ast}}^{2}$ and has rank $\leq n-1$. Now we are going to prove that it has rank $\geq n-1$.
Let $\pi_{1}:T\rightarrow T_{1}$ be the projection of the $k$-vector space $T=T_{0}\oplus T_{1}\oplus T_{2}\oplus...$ onto its $1$st graded component $T_{1}$. Let $\iota_{1}:T_{1}\rightarrow T$ be the canonical inclusion. Then, the map $\iota_{1}\circ\pi_{1}:T\rightarrow T$ sends every element of $T$ to its first graded component (viewed as an element of $T$).
Notice that for every $\left( i_{1},i_{2},...,i_{n}\right) \in\mathbb{N} ^{n}$, the map $\xi_{1}^{i_{1}}\xi_{2}^{i_{2}}...\xi_{n}^{i_{n}}$ sends every polynomial to its coefficient before $X_{1}^{i_{1}}X_{2}^{i_{2}} ...X_{n}^{i_{n}}$. Hence, the elements $\xi_{1}$, $\xi_{2}$, $...$, $\xi_{n}$ of $T^{\ast}$ are algebraically independent. Let $L$ be the $k$-subspace of $T^{\ast}$ they generate. Then, it is clear that $L$ consists of all $k$-linear maps $\phi:T\rightarrow k$ which are zero on all but the $1$st graded components of $T$. Hence, for every map $\phi\in T^{\ast}$, the map $\phi\circ\iota_{1}\circ\pi_{1}$ belongs to $L$.
Now, assume that $f_{n}$ has rank $ < n-1$. Then, we can write $f_{n}$ in the form $f_{n}=\sum\limits_{i=1}^{m}\lambda_{i}g_{i}h_{i}$ with $\lambda_{i}\in k$, $g_{i}\in\overline{T^{\ast}}$ and $h_{i}\in\overline{T^{\ast}}$ for some $m < n-1$. Now, it is easy to see that the equation $f_{n}=\sum\limits_{i=1} ^{m}\lambda_{i}g_{i}h_{i}$ remains true if we replace all $g_{i}$ by $g_{i}\circ\iota_{1}\circ\pi_{1}$ and replace all $h_{i}$ by $h_{i}\circ \iota_{1}\circ\pi_{1}$. (In fact, to prove that it remains true, just check it on every graded component of $T$ separately, using the gradedness of the comultiplication and the fact that $g_{i}$ and $h_{i}$ are zero on $T_{0}$.) But this replacement has the effect that the new $g_{i}$ and $h_{i}$ belong to $L$ (because for every map $\phi\in T^{\ast}$, the map $\phi\circ\iota _{1}\circ\pi_{1}$ belongs to $L$).
Thus we have written $f_{n}$ in the form $f_{n}=\sum\limits_{i=1}^{m} \lambda_{i}g_{i}h_{i}$ with $\lambda_{i}\in k$, $g_{i}\in L$ and $h_{i}\in L$ for some $m < n-1$. Since $\xi_{1}$, $\xi_{2}$, $...$, $\xi_{n}$ are algebraically independent, we can view them as polynomial indeterminates, and then the equation $f_{n}=\sum\limits_{i=1}^{m}\lambda_{i}g_{i}h_{i}$ becomes a
polynomial identity between the polynomial $f_{n}=\sum\limits_{1\leq i < j\leq n}\xi_{i}\xi_{j}$ and the polynomial $\sum\limits_{i=1}^{m}\lambda_{i} g_{i}h_{i}$, where $g_{i}$ and $h_{i}$ are homogeneous polynomials of degree $1$ in $\xi_{1}$, $\xi_{2}$, $...$, $\xi_{n}$ (because they lie in $L=\left\langle \xi_{1},\xi_{2},...,\xi_{n}\right\rangle $). Now, since homogeneous polynomials of degree $2$ are quadratic forms, and homogeneous polynomials of degree $1$ are linear forms, we can rewrite this result in a linear-algebraic way: The quadratic form $\sum\limits_{1\leq i < j\leq n}\xi _{i}\xi_{j}$ on the vector space $k^{n}$ can be written as a $k$-linear combination of $m$ products of linear forms $g_{i}$ and $h_{i}$. As a consequence, of course, the quadratic form $\sum\limits_{1\leq i < j\leq n} \xi_{i}\xi_{j}$ must be zero on the intersection $\bigcap\limits_{i=1} ^{m}\operatorname*{Ker}g_{i}$. Since $\bigcap\limits_{i=1}^{m}
\operatorname*{Ker}g_{i}$ is a subspace of $k^{n}$ of dimension at least $2$ (because $m < n-1$), this yields that the quadratic form $\sum\limits_{1\leq i < j\leq n}\xi_{i}\xi_{j}$ is zero on some subspace of $k^{n}$ of dimension at least $2$. On the other hand, since $k=\mathbb{R}$, we know that the quadratic form $\sum\limits_{1\leq i < j\leq n}\xi_{i}\xi_{j}$ is negative definite on some subspace of $k^{n}$ of dimension $n-1$ (see, for instance, Theorem 2 in http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2429180#p2429180 ). The intersection of these two subspaces is nonzero (since $2+\left( n-1\right) >n$), and on this intersection we get a contradiction. This falsifies our assumption that $f_{n}$ have rank $ < n-1$. Thus, $f_{n}$ must have rank exactly $n-1$, and §2 is proven.
[Note that we used $k=\mathbb{R}$ here, but for an arbitrary $k$ we could still have proven that $f_{n}$ has rank between $\dfrac{n}{2}$ and $n-1$, and this would still be enough for the below argument once some minor changes are made.]
§3. Let $C$ be a graded coalgebra. Let $m\in\mathbb{N}$ be positive. Then, we define a graded coalgebra $C_{\left( m\right) }$ as the coalgebra $C$ with the following new grading: $\left( C_{\left( m\right) }\right) _{i}=\left\{ \begin{array} {c} C_{i/m}\text{, if }m\mid i;\\ 0\text{, if }m\nmid i \end{array} \right. $ for all $i\in\mathbb{N}$.
It is clear that this new graded coalgebra $C_{\left( m\right) }$ is well-defined, and if $C$ is connected, then $C_{\left( m\right) }$ is also connected.
§4. Some notations: For every connected graded coalgebra $C$, let $C^{+}$ denote the positive part of $C$ (that is, the subspace $C_{1}\oplus C_{2}\oplus C_{3}\oplus...=\operatorname*{Ker}\varepsilon$), and for every $c\in C^{+}$, we denote the element $\Delta\left( c\right) -c\otimes 1-1\otimes c$ of $C^{+}\otimes C^{+}$ (proving that this element indeed lies in $C^{+}\otimes C^{+}$ is a nice exercise) by $\overline{\Delta}\left( c\right) $.
§5. Let $C_{\left[ 1\right] }$, $C_{\left[ 2\right] }$, $C_{\left[ 3\right] }$, $...$ be graded coalgebras (I use the square brackets in $C_{\left[ n\right] }$ to distinguish it from an $n$-th graded component of something). Then the direct sum $C_{\left[ 1\right] }\oplus C_{\left[ 2\right] }\oplus C_{\left[ 3\right] }\oplus...$ is a graded coalgebra as well, but not connected even if $C_{\left[ 1\right] }$, $C_{\left[ 2\right] }$, $C_{\left[ 3\right] }$, $...$ are. Instead, we can define a "connected graded sum" of connected graded coalgebras $C_{\left[ 1\right] } $, $C_{\left[ 2\right] }$, $C_{\left[ 3\right] }$, $...$ as follows:
Consider the direct sum $k\oplus C_{\left[ 1\right] }^{+}\oplus C_{\left[ 2\right] }^{+}\oplus C_{\left[ 3\right] }^{+}\oplus...$ of $k$-vector spaces, graded just like every other direct sum of graded $k$-vector spaces (the $k$, $C_{\left[ 1\right] }^{+}$, $C_{\left[ 2\right] }^{+}$, $C_{\left[ 3\right] }^{+}$, $...$ are not the graded components). For every $n\in\mathbb{N}$, we can consider the $k$-vector space $C_{\left[ n\right] }=k\oplus C_{\left[ n\right] }^{+}$ as a subspace of this direct sum (because both $k$ and $C_{\left[ n\right] }^{+}$ are summands). We define the coalgebra structure on $k\oplus C_{\left[ 1\right] }^{+}\oplus C_{\left[ 2\right] }^{+}\oplus C_{\left[ 3\right] }^{+}\oplus...$ in such a way that $C_{\left[ n\right] }$ becomes a subcoalgebra for every $n\in\mathbb{N}$. (This is easily seen to be well-defined.) This new graded coalgebra is connected.
§6. If $C_{\left[ 1\right] }$, $C_{\left[ 2\right] }$, $C_{\left[ 3\right] }$, $...$ are locally finite connected graded coalgebras, then $k\oplus C_{\left[ 1\right] }^{+}\oplus C_{\left[ 2\right] }^{+}\oplus C_{\left[ 3\right] }^{+}\oplus...$ needs not be locally finite. However, $k\oplus C_{\left[ 1\right] \left( 1\right) }^{+}\oplus C_{\left[ 2\right] \left( 2\right) }^{+}\oplus C_{\left[ 3\right] \left( 3\right) }^{+}\oplus...$ is a locally finite connected graded coalgebra.
§7. Now to the counterexample. Let $k=\mathbb{R}$. For every positive $n\in\mathbb{N}$, let $\left( C_{\left[ n\right] },f_{n}\right) $ be a pair of a locally finite connected graded $k$-coalgebra $C_{\left[ n\right] }$ and a map $f_{n}\in\overline{C_{\left[ n\right] }^{\ast}}^{2}$ of rank $n-1$. (Such a pair exists because we can take the pair $\left( T,f_{n}\right) $ of §2.)
Then, $k\oplus C_{\left[ 1\right] \left( 1\right) }^{+}\oplus C_{\left[ 2\right] \left( 2\right) }^{+}\oplus C_{\left[ 3\right] \left( 3\right) }^{+}\oplus...$ is a locally finite connected graded coalgebra. Denote it by $C$. Let $f\in\overline{C^{\ast}}$ be the $k$-linear map which acts as $0$ on $k$ and acts as $f_{n}$ on each $C_{\left[ n\right] }^{+}$ (we don't have to distinguish between $C_{\left[ n\right] }^{+}$ and $C_{\left[ n\right] \left( n\right) }^{+}$ here, since we are not talking about the grading). This map $f$ maps every primitive element of $C$ to $0$ (in fact, every primitive element of $C$ is a sum of primitive elements of some $C_{\left[ n\right] \left( n\right) }^{+}$'s, and each of them is mapped to $0$ by the respective $f_{n}$ because $f_{n}\in\overline{C_{\left[ n\right] }^{\ast} }^{2}$). If our assertion was true, then this map $f$ would lie in $\overline{C^{\ast}}^{2}$, and thus have a rank. Denote by $N$ this rank. We could thus write the map $f$ in the form $f=\sum\limits_{i=1}^{N}\lambda _{i}g_{i}h_{i}$ with $\lambda_{i}\in k$, $g_{i}\in\overline{C^{\ast}}$ and $h_{i}\in\overline{C^{\ast}}$. Now, for every positive $n\in\mathbb{N}$, we could restrict both sides of the equation $f=\sum\limits_{i=1}^{N}\lambda _{i}g_{i}h_{i}$ to the subcoalgebra $k\oplus C_{\left[ n\right] \left( n\right) }^{+}$ of $C$ (this subcoalgebra is isomorphic to $C_{\left[ n\right] }$, at least if we don't care about the grading), and thus conclude that $f_{n}=\sum\limits_{i=1}^{N}\lambda_{i}\left( g_{i}\mid_{k\oplus C_{\left[ n\right] \left( n\right) }^{+}}\right) \left( h_{i} \mid_{k\oplus C_{\left[ n\right] \left( n\right) }^{+}}\right) $, so that $f_{n}$ has rank $\leq N$. But this is nonsense since the rank of $f_{n}$ is known to be $n-1$, and $n-1>N$ for $n$ sufficiently large. This contradiction proves the counterexample.
