You are correct that you have to be careful when inserting the EOM back into the Lagrangian since you can generate non-local interactions. To see how this works, and what you must assume, we can consider a Yukawa theory with a massive scalar interaction
\begin{equation}
\mathcal{L} = i\overline{\psi}\gamma^\mu\partial_\mu\psi - \frac{1}{2}\phi(\Box+m^2)\phi + \lambda\phi\overline{\psi}\psi.
\end{equation}
We want to match this $\mathcal{L}$ to an effective Lagrangian $\mathcal{L}_\text{eff}$ that does not have the scalar field in it where the effective Lagrangian will be useful for energies that are $E\ll m$. For large $m$, the fluctuations of $\phi$ around its classical configurations are surpressed. The classical equations of motion for the scalar field is
\begin{equation}
\phi = \frac{\lambda}{\Box+m^2}\overline{\psi}\psi
\end{equation}
and that loop corrections of $\phi$ are assumed to be small. We can plug the classical equations of motion back into the Lagrangian to get
\begin{align}
\mathcal{L}_\text{eff} & = i\overline{\psi}\gamma^\mu\partial_\mu\psi + \frac{\lambda^2}{2}\overline{\psi}\psi\frac{1}{\Box+m^2}\overline{\psi}\psi\\
& = i\overline{\psi}\gamma^\mu\partial_\mu\psi + \frac{\lambda^2}{2m^2}\overline{\psi}\psi\overline{\psi}\psi - \frac{\lambda^2}{2m^4}\overline{\psi}\psi\Box\overline{\psi}\psi + \cdots
\end{align}
In the first line, the insertion of the $\phi$-equations of motion gurantees that we have the same correlation functions as $\mathcal{L}$ but with no $\phi$. The Taylor expansion performed is under the assumption that $m$ is larger than the momentum scales we are probing, which gives rise to the non-local effective Lagrangian as a series of operators you see.
In setting $\phi$ to its classical equations of motion, all this amounts to at the level of the path integral is by computing the steepest descent approximation. This is how the effective action is normally defined too with the path integral.
Hopefully that answered some of your questions. A more physical (realistic) example is by setting the scalar here $\phi$ to be the $W$ or the $Z$ boson, since integrating out those bosons gives you the 4-Fermi theory where every operator in 4-Fermi is then suppressed by powers of $E^2/m_W^2$ at low energies.
(Note: I believe you can also integrate out the Fermions if you would like to, but this just gives a different effective field theory. But the EFT from integrating out the scalar or the fermion both have a "UV" completion of the original Lagrangian.)
