In a classic Georgi review of EFT, I have read the following quote
The result of eliminating heavy particles is inevitably a nonrenormalizable theory, in which the nontrivial effects of the heavy particles appear in interactions with dimension higher than four. In the full theory, these effects are included in the nonlocal interactions obtained by integrating out the heavy particles. These interactions, because of their nonlocal nature, get cut off for energies large compared to the heavy particle masses. However, in the effective theory, we replace the nonlocal interactions from virtual heavy particle exchange with a set of local interactions, constructed to give the same physics at low energies. In the process, we have modified the high energy behavior of the theory, so that the effective theory is only a valid description of the physics at energies below the masses of the heavy particles. Thus the domain of utility of an effective theory is necessarily bounded from above in energy scale.
Why are the new interactions, obtained in the EFT by integrating out the heavy fields, nonlocal? I can't see this as a direct consequence of the nonrenormalizability of the interaction or of the fact that it depends on the exchanged momentum.
I do understand that interactions mediated by massive particles are shortrange because the corresponding effective potential is damped by a real exponential term -- but don't know if this has anything to do with my doubt and think that perhaps I'm confusing the concepts of 'local' and 'short range'.
Then, in the phrase
However, in the effective theory, we replace the nonlocal interactions from virtual heavy particle exchange with a set of local interactions, constructed to give the same physics at low energies.
I believe that Georgi is talking about the fact that we expand that new effective interaction in powers of $\left( \frac{p^2}{M^2}\right)$.
Why is the expanded perturbative interaction, now, local?