The key thing is that you need to be working with canonically normalized fields in order to use the power counting arguments.
Let's expand GR around flat space
\begin{equation}
g_{\mu\nu} = \eta_{\mu\nu} + \tilde{h}_{\mu\nu}
\end{equation}
The reason for the tilde will become clear in a second. So long as $\tilde{h}$ is "small" (or more precisely so long as the curvature $R\sim (\partial^2 \tilde{h})$ is "small"), we can view GR as an effective field theory of a massless spin two particle living on flat Minkowski space.
Then the Einstein Hilbert action takes the schematic form
\begin{equation}
S_{EH}=\frac{M_{pl}^2}{2}\int d^4x \sqrt{-g} R = \frac{M_{pl}^2}{2} \int d^4x \ (\partial \tilde{h})^2 + (\partial \tilde{h})^2\tilde{h}+\cdots
\end{equation}
where $M_{pl}\sim 1/\sqrt{G}$ in units with $\hbar=c=1$. $M_{pl}$ has units of mass. In this form you might thing that the interaction $(\partial \tilde{h})^2 \tilde{h}$ comes with a scale $M^2_{pl}$ with a positive power. However this is too fast--all the QFT arguments you have seen have assumed that the kinetic term had a coefficient of -1/2, not $M_{pl}^2$. Relatedly, given that $M_{pl}$ has units of mass and the action has units of $(mass)^4$, the field $\tilde{h}$ is dimensionless, so it is clearly not normalized the same way as the standard field used in QFT textbooks.
Now classically, the action is only defined up to an overall constant, so we are free to think of $M_{pl}^2$ as being an arbitrary constant. However, in QFT, the action appears in the path integral $Z=\int D\tilde{h}e^{iS[\tilde{h}]/\hbar}$ (note the notational distinction between $\tilde{h}$ and $\hbar$). Thus the overall constant of the action is not a free parameter in QFT, it is fixed and has physical meaning. Alternatively, you have to remember that the Einstein Hilbert action will ultimately be coupled to matter; when we do that, the scale $M_{pl}$ sitting in front of $S_{EH}$ will not multiply the matter action, and so $M_{pl}$ sets the relative scale between the gravitational action and the matter action.
The punchline is that we can't simply ignore the overall scale $M_{pl}^2$, it has physical meaning (ie, we can't absorb $M_{pl}$ into an overall coefficient multiplying the action). On the other hand, we want to put the action into a "standard" form where the overall scale isn't there, so we can apply the normal intuition about power counting. The solution is to work with a "canononically normalized field" $h$, related to $\tilde{h}$ by
\begin{equation}
\tilde{h}_{\mu\nu} = \frac{h_{\mu\nu}}{M_{pl}}
\end{equation}
Then the Einstein Hilbert action takes the form
\begin{equation}
S_{EH} = \int d^4 x \ (\partial h)^2 + \frac{1}{M_{pl}} (\partial h)^2 h + \cdots
\end{equation}
In this form it is clear that the interactions of the form $(\partial h)^2 h$ have a "coupling constant" $1/M_{pl}$ with dimensions 1/mass, which is non-renormalizable by power counting in the usual way.
I think it's quite easy to prove with functional integrals. In Wilson renormalization one splits the field in low energy modes and high energy ones, say $\phi = \varphi + \Phi$, where $\varphi$ only has support on small momenta and $\Phi$ on large ones. The action will be $S[\varphi,\Phi] = S_1[\varphi] + S_2[\Phi] + S_\text{int}[\varphi,\Phi]$.
Imagine now that the full theory (high energy) has a symmetry under $\varphi \to \tilde\varphi[\varphi]$ and $\Phi \to \tilde\Phi[\Phi]$. This means that the action is invariant: $S[\tilde\varphi,\tilde\Phi]=S[\varphi,\Phi]$. Note also that I've used the fact that internal symmetries do not mix low energy modes with high energy ones. EDIT: To understand this one can work, for example, in momentum space. The low and high energy modes are defined such that
$$
\varphi(k) = \begin{cases} \phi(k) \quad \text{ for } k \leq \Lambda \\
0 \quad \quad \,\text{ otherwise}\end{cases}\,, \qquad \Phi(k) = \begin{cases} 0 \quad\quad\,\, \text{ for } k \leq \Lambda \\
\phi(k) \quad \,\text{ otherwise}\end{cases}\,.
$$
Since internal symmetries do not act on the momenta, but only on the indices of the fields, the transformed of, for example, $\varphi(k)$ will still have only support on $k\leq \Lambda$, i.e. it will still be a low energy mode. END OF EDIT
Now, the effective action obtained integrating over high energy modes, is defined as
$$
e^{iS_\text{eff}[\varphi]} = e^{iS_1[\varphi]}\int \mathcal{D}\Phi \, \exp \left( iS_2[\Phi]+iS_\text{int}[\varphi,\Phi] \right)\,.
$$
Now, perform a symmetry transformation on $\varphi$,
\begin{align}
e^{i S_\text{eff}[\tilde\varphi]} &= e^{iS_1[\tilde \varphi]} \int \mathcal{D}\Phi \exp\left( iS_2[\Phi] + i S_\text{int}[\tilde\varphi,\Phi]\right) \\
&= e^{iS_1[\tilde \varphi]} \int \mathcal{D}\tilde\Phi \exp\left( iS_2[\tilde\Phi] + i S_\text{int}[\tilde\varphi,\tilde\Phi]\right) \\
&= e^{iS_1[\varphi]} \int \mathcal{D}\Phi \exp\left( iS_2[\Phi] + i S_\text{int}[\varphi,\Phi]\right)= e^{iS_\text{eff}[\varphi]}\,,
\end{align}
where in the second equality I've just performed a change of integration variable $\Phi\to\tilde\Phi$, and in the third I've used the fact that the action is invariant and the symmetry is not anomalous (i.e. $\mathcal{D}\Phi = \mathcal{D}\tilde\Phi$).
Therefore, if the original theory is invariant, the effective low energy one is invariant as well, i.e. no symmetry breaking terms can be generated in the renormalization procedure.
I hope this answers your question!
Best Answer
Typically, when you want to require a symmetry you choose to restrict the allowed terms in your Lagrangian to a smaller subset, this subset being the terms that are singlets under the symmetry group. For example, consider the Lagrangian of two fields $\phi_1$ and $\phi_2$. If it depends only on the combinations $$ \phi_1^2+\phi_2^2\,,\quad(\partial\phi_1)^2+(\partial\phi_2)^2\,, $$ then there is an $\mathrm{SO}(2)$ symmetry. This statement amounts to saying that terms such as $\phi^2_1$ or $\phi_1\phi_2$ are absent.
Now suppose that you write down all terms that involve the particles you are considering and which are relevant. Relevant here is meant in an RG sense, namely terms that survive in the infra-red. If all these terms happen to be singlets of a certain group, then so be it, your Lagrangian is going to have that symmetry. But it was not a deliberate choice, it's just what is forced upon you when you go to low energies.
Because of this fact such symmetries are called "accidental."
An example of this is QED which is $\mathsf{P}$ invariant but just because you can't write any $\mathsf{P}$-breaking term that has dimension below four which is made only of electrons and photons.