If $: V(\phi) :$ is non-local in space, does that mean interacting quantum field theory is non-local? Free field theories are definitely local in.
In the interaction picture, we can decompose the fields into creation operator modes and annihilation operator modes. The product of operators can be regulated to finiteness by Wick ordering. In Wick ordering, all creation operators are moved to the left of all annihilation operators.
To introduce interactions, we can add a Wick ordered interaction term $:V[\Phi(x)]:$ to the interaction Hamiltonian, but this term is nonlocal in space. To Wick order, we have to Fourier transform to momentum space, subtract some zero point terms, and then Fourier transform back to position space. The end result when expressed in terms of the original spatial fields is a nonlocal convolution with a spatially extended kernel.
Let me clarify a bit. For potentials which are quadratic in the fields, the zero point subtraction is just a c-number, and this is trivially local. But for quartic couplings, for example, the zero point subtraction we get from Wick ordering is still quadratic in the fields with nonlocal point splitting.
Does that mean interacting quantum field theory is nonlocal?
 A: No, it doesn't mean that quantum field theory is non-local. The fact that there exist operators that exactly (anti)commute at spacelike separation remains exactly valid at the interacting level.
Your argument is based on a flawed assumption. It is not true that the higher-order interaction term should be normal-ordered in the Hamiltonian. The right interaction Hamiltonian should be written "as it is", without normal ordering.
The derivation of Feynman rules for scattering amplitudes in the operator language and interaction picture requires us to calculate the matrix elements of $S$ in the initial and final state. The matrix $S$ is the time-ordered exponential:
$$ S \approx T \left[i \exp\int dt\,H_I \right] $$
Sorry if there should be $-i$ in front of $H_I$. There is no normal ordering in this formula which is why there's no non-locality of the interaction term; instead, there is time-ordering of everything.
Via Wick's theorem, this time-ordered exponential, when expanded via Taylor expansion, may be written via the contractions
$$ C(x_1,x_2) = \langle 0 | T (\phi_1 \phi_2) | 0\rangle = i\Delta_F(x_1-x_2)$$
which is the standard Feynman propagator, associated with $i/(k^2-m^2+i\epsilon)$ in the momentum space. But the contraction is the difference of the time-ordered (but not normal-ordered) product of two operators, which always appear in the definition of the S-matrix, and the normal-ordered (but no longer time-ordered) product, which is easy to deal with when evaluating the matrix elements.
Indeed, I think that if you added a higher-order interaction Hamiltonian with the extra normal ordering, you would get a non-local theory, but that's not how QFTs are defined.
You may be dissatisfied that without the normal ordering, the interaction Hamiltonian will lead to infinite matrix elements etc. Indeed, it will. But there are many other infinities of a similar kind and all of them have to be dealt with by the process of renormalization.
The idea that the interaction Hamiltonian should be normal-ordered is probably a flawed artifact of the intuition to get rid of the infinities "as soon as possible". For free quantum field theories, one may define finite prescriptions - without renormalization - for quantities such as the total energy and the total charge and normal ordering is helpful to do so easily.
But this treatment of free quantum field theories is not useful to get rid of many other infinities that appear once the interactions are included. To deal with them, one needs renormalization. Normal ordering of the interaction Hamiltonian is not only useless to get rid of the infinities: it would be harmful because, as you correctly observed, it would produce non-localities. (Unless the theory would be equivalent to a local field theory by a field redefinition, and I don't see an obvious way how it could happen.)
As far as I can see, this trivial mistake - making the interaction Hamiltonian normal-ordered - appears at some treatments of quantum field theory in the "axiomatic" or "algebraic" quantum field theory framework, which is why those approaches, at least in some of their versions, are completely incompatible both with renormalization as well as locality.
A: I agree with part of the answer by Motl that in the ordinary treatment of QFT, it's really the unordered polynomial $V(\phi)$ that's added to the free Hamiltonian.
But for what it's worth, I think the normal-ordered polynomial $N(V(\phi))$ actually is local.  Granted, you're right to worry a priori it might not be, because general sums of products of ladder operators really are non-local.  
Here's my argument $N(V(\phi))$ is local; correct me if I'm wrong.  Let's treat the case $V(\phi)=\phi^n$ for even $n$.  We'll argue by induction in even $n$. That is, assume we have proven $N(\phi^m)$ is local for all even $m<n$.  By Wick's theorem, say the version expressed here on Wikipedia, we have
$$ \phi^n = N(\phi^n) + \; const. \langle \phi^2 \rangle N(\phi^{n-2}) + \; const. \langle \phi^2 \rangle \langle \phi^2 \rangle  N(\phi^{n-4}) \, + ... .$$
The LHS is local, and all the terms after the first on the RHS are local by the inductive hypothesis, so $N(\phi^n)$ must be local. 
Moreover, if you stare at the above, you can conclude
$$ N(\phi^n) = \phi^n + A_{n-2} \phi^{n-2} + A_{n-4} \phi^{n-4} + … + A_0$$
for some constants $A_{n-2},...,A_0.$
So it's also clear from this expression that $N(\phi^n)$ is local.
The argument for odd powers is similar.
