Why are infinite order Lagrangians called 'non-local'? And in what sense are they 'non-local'?
 A: This is the first time I write an answer here. Tell me if it's bad or if I did something wrong.
I think I can contribute something here:
My mental image is the following:
A simple derivative is
$$ f'(x) = \lim_{h\to 0} \frac{f(x+h) - f(x)}{h}\,, $$
for the second derivative
$$ f''(x) = \lim_{h\to 0} \frac{f(x+2h) -f(x+h) + f(x)}{h^2}\,,$$
and so on....
Now if you have a function like $e^{\Theta\partial_x^2}$ acting on f(x)
you have an infinite amount of derivatives, this means you will go out to $f(x + \infty h)$ (don't hurt me, this is just for the mental image) and the limit $\lim_{h\to 0} f(x+\infty h)$ gives an idea that the value of
$$e^{\Theta \partial_x^2}f(x)$$
does depend on more than the point x (or a neighbourhood of it), but maybe whole $\mathbb{R}$. This could be done more rigorous I think.
Every single term of the Taylor expansion
$$ e^{\Theta\partial_x^2} = \sum_{i=0}^{\infty} \frac{(\Theta\partial_x^2)^i}{i!}$$
is local, since it only contains a finite amount of derivatives. The 'last' term with infinitely many derivatives is nonlocal. With this I want to say that truncating the expansion of a nonlocal term can make the nonlocal effects vanish.
The other way of seeing the nonlocality is by Fourier Transforming and inverse Fourier Transforming:
$$ e^{\Theta \partial_x^2} f(x) = e^{\Theta \partial_x^2} \int \frac{\mathrm{d}p}{\sqrt{2\pi}}e^{i x p} \tilde{f}(p) \\ = 
  \int \frac{\mathrm{d}p}{\sqrt{2\pi}}e^{-\Theta p^2} e^{i x p} \tilde{f}(p) \\
\int \frac{\mathrm{d}p}{\sqrt{2\pi}}e^{-\Theta p^2} e^{i x p} \int\frac{\mathrm{d}y}{\sqrt{2\pi}} e^{-i y p} f(y) \\
= \int \frac{\mathrm{d}p\,\mathrm{d}y}{2\pi} e^{-\Theta p^2 + i p (x-y)} f(y) \\ 
= \frac{1}{2\pi} \sqrt{\frac{\pi}{\Theta}} \int \mathrm{d}y\, e^{-\frac{(x-y)^2}{4 \Theta}} f(y)\,. $$
Thus the nonlocal operator $e^{\Theta \partial_x^2}$ is equivalent to the convolution with a gaussian kernel which is clearly nonlocal since it is an integral over $\mathbb{R}$. If you can solve the $p$ integral this should be possible of every nonlocal operator?
A: The higher the number of derivatives the more initial data you have to provide. If you have some Lagrangian that contains an infinite number of derivatives (or derivatives appearing non-polynomially, such as one over derivative) then you have to provide an infinite amount of initial data which amounts to non-local info, in the sense explained below. 
If you think in terms of Taylor expansions around your initial value, then you have to provide the full function (and thus non-local information) if you have an infinite number of derivatives. This is to be contrasted with cases where you provide only the field and its first derivative as initial values (and thus rather local information).
Personally, I would not call any higher-derivative Lagrangian "non-local", but only those theories where the number of derivatives is formally infinite in the Lagrangian. 
In any discretization scheme you literally see the non-locality induced by higher derivatives: to define the first derivative you need to know the function on two adjacent lattice points, to define the second derivative on three and to define the n-th derivative on n+1 lattice points. Thus, the more derivatives the more non-locality. If you have an infinite number of derivatives you need to know the function on an infinite set of lattice points.
A: Just for info: there is a so called shift operator $\text{e}^{h\frac{d}{dx}}$ that shifts a function argument to another point, for example: $\phi(x+h)=\text{e}^{h\frac{d}{dx}}\phi(x)$. It is obvious that it contains an infinite number of differential operators for any function $\phi(x)$.
A: Clearly, an interaction involving $\phi(x+h)$ deserved to be called nonlocal. But since $\phi(x+h)=\sum_{k=0}^\infty \phi^{(k)}(x) h^k/k!$, any nonlocal interaction can be expressed as a power series involving arbitrarily many derivatives. Therefore an action (or Lagrangian) is called nonlocal if it involves infinitely many derivatives. 
If there are only finitely many derivatives, they are not nonlocal. Indeed, by introcing additional fields for the derivatives togetyher with squares of the differences between the new fields and their definition, one can rewrite these in terms of a new action/Lagrangian which leads to identical equations of motions.
(Unfortunately, this doesn't help with quantization, as the corresponding Legendre transformations to the Hamiltonian form is singular.)
A: Disillusionment with systems described by higher order Lagrangians harks back to a 1950 paper by Pais and Uhlenbeck, in which they showed that such systems were prone to pathologies, including states with negative energy and states with negative norm. There's a more recent discussion of this in arXiv:hep-th/0408104.
