No, there is not always such an approximate unit. (This will be easier to formulate in terms of left modules, and with inner products linear in the first entry. The warning seems necessary due to the common convention in C*-module theory to do the opposite.)
Example
Let $A=B(\mathbb{C}^2)$ (linear operators), $E=\mathbb{C}^2$, with the module action given by operators acting on vectors (on the left) and the $A$-valued inner product of $x$ and $y$ in $E$ given by $<x,y>_A(z)=<z,y>_\mathbb{C}x$. Then $<x,y>_A$ has rank at most one for all $x$ and $y$, so no such approximate identity exists. $\square$
Any finite dimensional Hilbert space with dimension at least 2 would give a slight modification of this example. Or, let $E=H$ be a separable, infinite dimensional Hilbert space, and let $A=\mathcal{K}(H)$ be the algebra of compact operators on $H$. (Added: Note that fullness follows from the fact that the span of the range of the inner product is the set of finite rank operators.) Or, given a C*-algebra $B$, one could form $H_B=B\oplus B\oplus\ldots$ with its usual right $B$-module structure and consider the analogous construction with $A=\mathcal{K}(H_B)$ and $E=H_B$. If $B$ is $\sigma$-unital, then so is $A$, but there will be no approximate identity of the desired form.
I do not have anything useful to say about formulating sufficient conditions for such an approximate identity to exist, but this simple example shows that lack of existence is common.