Edit: even if another answer has been accepted, I edited mine in order to correct (hopefully) the issues raised in the comments, and
- possibly list more easily readable references to Łojasiewicz's solution of the division problem, and
- prove that the tempered distribution $S$, found by using Łojasiewicz's division theorem and such that $\phi\ast S=\phi\ast E$, is equal to $E$.
- prove a stronger property that the one required by the asker: namely, if $\phi\ast E\in\mathscr{S}^\prime$ for a single function $\phi\in C^\infty_c(\Bbb R^n)$, then $E\in\mathscr{S}^\prime$.
The result can be proved by using Stanisław Łojasiewicz's solution of the division problem in $\mathscr{S}^\prime(\Bbb R^n)$ (see [2] and [3] or [4] pp. 99-101 or [6] chapter VI, §VI.1): the equation
$$
\Phi S=T\label{div}\tag{DIV}
$$
has a tempered distribution solution $S\in\mathscr{S}^\prime(\Bbb R^n)$ for every non-null real analytic function $\Phi\in \mathscr{A}(\Bbb R^n)$ and every datum $T\in\mathscr{S}^\prime(\Bbb R^n)$. Indeed, since
$$
G_\phi=\phi \ast E\in L^2(\Bbb R^n)\qquad \forall \phi\in C_c^\infty(\Bbb R^n),
\label{1}\tag{1}
$$ we have also that $G_\phi\in\mathscr{S}^\prime(\Bbb R^n)$ as a distribution, and thus $\hat{G}_\phi\in\mathscr{S}^\prime(\Bbb R^n)$ by the isomorphism theorem for the Fourier transform in $\mathscr{S}^\prime$ (see [1], chapter VII, §7.1, theorem 7.1.10, p. 164). Then we can choose a test function $\phi\not\equiv 0$ and, by using the division theorem, find a tempered distribution $S$ such that
$$
\hat{\phi}\hat{S}=\hat{G}_\phi\label{2}\tag{2}
$$
since
$$
\phi\in C_c^\infty(\Bbb R^n) \implies\phi\in \mathscr{E}^\prime(\Bbb R^n)
$$ as a distribution, and therefore $\hat{\phi}\in \mathscr{A}(\Bbb R^n)$ i.e. $\hat{\phi}$ is a complex valued real analytic function (see, for example, [1], chapter VII, §7.1, theorem 7.1.14 pp. 165-166). Now applying the inverse Fourier transform to both sides of equation \eqref{2} and considering equation \eqref{1} we have
$$
\phi\ast S=\phi\ast E\iff \phi\ast(S-E)=(S-E)\ast\phi =0 \label{3}\tag{3}
$$
Lemma. Equation \eqref{3} implies $S=E$.
Proof for a given $\phi\in C^\infty_c(\Bbb R^n)$, consider the following convolution equation: $\DeclareMathOperator{\invs}{\small{inv}}$
$$
\phi\ast\psi(x)=-\varphi(-x)=-\varphi\circ\invs(x) \quad \forall \varphi(x)\in C^\infty_c\Bbb R^N \label{4}\tag{4}
$$
where $\Bbb R^n \ni x\mapsto \invs(x)=-x$ is the point reflection map. Again by the division theorem, this equation is solvable and its solution, i.e.
$$
\psi(x)= -\mathscr{F}^{-1} \left[\hat{\phi}^{-1}\right] \ast \varphi\circ\invs(x)
$$
apart from being tempered as a distribution, is a $C^\infty$ function since it is equal to the convolution of a tempered distribution whit a compactly supported and $C^\infty$-smooth function. Now define $\eta_r\in C_c^\infty(\Bbb R^n)$, $r>0$, as
$$
\eta_r(x) =
\begin{cases}
1 & |x|<r\\
0\le\text{ and }< 1 & r\le |x|\le r+1\\
0 & |x|>r+1,
\end{cases}
$$
Then the family
$$
\{\psi_r(x)\}_{r>0}=\{\eta_r(x)\cdot\psi(x)\}_{r>0}
$$ is a family of compactly supported $C^\infty$ functions converging to $\psi$.
Now consider the structure of the convolution on the left side of \eqref{3}: we have that
$$
(S-E)\ast \phi = \big\langle S-E ,\phi(x-\cdot)\big\rangle
$$ and thus
$$
\begin{split}
\langle (S-E)\ast \phi, \varphi\rangle & = \int_{\Bbb R^n}\langle S-E ,\phi(x-\cdot)\rangle\varphi(x)\mathrm{d} x\\
& = \left\langle S-E,\int_{\Bbb R^n}\phi(x-y)\varphi(x)\mathrm{d} x\right\rangle\\
& = \big\langle E- S,\phi\ast\varphi\circ\invs\big\rangle
\end{split}\label{5}\tag{5}
$$
so, again considering the relation \eqref{3} and the definition of the family of compactly supported functions $\{\psi_r(y)\}_{r>0}$ we have
$$
\begin{split}
\lim_{r\to+\infty}\big\langle (S-E)\ast \phi,\psi_r\big\rangle=\langle S-E,\varphi\rangle=0\quad \forall \varphi\in C_c^\infty(\Bbb R^n)
\end{split}
$$
and thus $E-S=0\iff E=S\;\blacksquare$.
Finally, the above lemma implies $E=S\iff E\in\mathscr{S}^\prime$.
Notes.
- The expositions for Łojasiewicz's solution of the division problem, apart from the original works [2] and [3] are the books by Bernhard Malgrange [4] and Jean-Claude Tougeron [5] (the latter two deal with the work of Malgrange which generalizes Łojasiewicz's solution to systems and even to $C^\infty$ division in some special cases): however, neither of them is particularly readable to the accustomed to the "ordinary" theory of distributions and its application, since the techniques used are more from the theory of analytic sets (varieties) and from the (however related) theory of ideals of smooth functions than from functional analysis. Nevertheless I like the work of Malgrange [4], partly because of its generality and partly because of its newly improved digital version produced by the Tata Institute of Fundalmental research. However, as stated above, they are not easy read.
- Jochen Bruning and iolo point out that the solution of \eqref{4} is unique if we chose $\phi$ in such a way that $\hat{\phi}(\xi)>0$ for all $\xi\in\Bbb R^n$: this is alway possible by the Paley-Wiener theorem.
- The relation \eqref{5} can also be proved directly by using the standard definition of convolution of distributions: however, using the fact that $\varphi\in C^\infty_c$ simplifies bit the formal development.
References
[1] Lars Hörmander (1990), The analysis of linear partial differential operators I, Grundlehren der Mathematischen Wissenschaft, 256 (2nd ed.), Berlin-Heidelberg-New York: Springer-Verlag, ISBN 0-387-52343-X/ 3-540-52343-X, MR1065136, Zbl 0712.35001.
[2] Stanisław Łojasiewicz (1959), "Sur le problème de la division" (French),
Studia Mathematica 18, 87-136, DOI: 10.4064/sm-18-1-87-136, MR0107168, Zbl 0115.10203.
[3] Stanisław Łojasiewicz, Sur le problème de la division, (French), Rozprawy Matematyczne 22, pp. 57 (1961), MR0126072, Zbl 0096.32102.
[4] Bernard Malgrange, Ideals of differentiable functions, (English) Studies in Mathematics. Tata Institute of Fundamental Research 3. London: Oxford University Press, pp. 106 (1966), MR0212575, Zbl 0177.17902.
[5] Jean-Claude Tougeron, Ideaux de fonctions différentiables (French) Ergebnisse der Mathematik und ihrer Grenzgebiete. Band 71. Berlin-Heidelberg-New York: Springer-Verlag. pp. VII+219 (1972), MR0440598, Zbl 0251.58001.