Why are infinite order Lagrangians called 'non-local'?

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.

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.)

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.