To completely localize a string within any bounded region of space, no matter how large, requires an infinite energy. Does this mean strings modes are inherently nonlocal?
Yes (formally) and no (physically).
The full extent of a string with finite energy is infinitely large; the expectation value of $\int d\sigma (x^i(\sigma))^2$ is proportional to $\sum 1/n$ and is logarithmically divergent. However, the contributions that make it infinitely large arise from very high-energy vibrations of the string, i.e. high values of the Fourier mode label $n$. And these vibrations are so fast that they average out.
So if one will study the "size" of a string with any other finite-energy probe, she will inevitably find out that the string is effectively finite. As a result, the scattering amplitudes in perturbative string theory actually strictly obey some inequalities that one may derive to hold in any local theory. In some sense, string theory saturates them.
The divergent value of the string's radius is also a perturbative artifact. It's clear that when the string coupling constant is nonzero, the highly excited modes become unstable and introduce an effective cutoff on the world sheet, anyway.
String theory is local in some other senses, too. Physics is local on the world sheet. So if one acknowledges that a string is an extended object, physical phenomena become completely local in spacetime once again. Because of the arguments two paragraphs above, some locality is preserved even if we associate every string with its center of mass.
The same non-locality discussion applies not only to strings but also to arbitrary bound states in BFSS-like matrix models of string/M-theory. In those cases, one may also see that the size of the bound states - the whole "clouds" - is infinitely large in the relevant large $N$ limit. However, these large clouds will also penetrate through one another because the effect of very distant loci of the clouds (from the center) is associated with very fast vibrations that get rapidly averaged out.