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.