Presuming that there aren't nonlocal constraints, a differential operator that is polynomial in differential operators is local, it doesn't have to be quadratic. My understanding is that irrational or transcendental functions of differential operators are generally nonlocal (though that's perhaps a Question for math.SE).
A given space of solutions implies a particular nonlocal choice of boundary conditions, unless the equations are on a compact manifold (which, however, is itself a nonlocal structure). There is always an element of nonlocality when we discuss solutions in contrast to equations.
[For the anti-locality of the operator $(-\nabla^2+m^2)^\lambda$ for odd dimension and non-integer $\lambda$, one can see I.E. Segal, R.W. Goodman, J. Math. Mech. 14 (1965) 629 (for a review of this paper, see here).]
EDIT: Sorry, I should have gone straight to Hegerfeldt's theorem. Schrodinger's equation is enough like the heat equation to be nonlocal in Hegerfeldt's sense. There are two theorems, from 1974 in PRD and from 1994 in PRL, but in arXiv:quant-ph/9809030 we have, of course with references to the originals,
Theorem 1. Consider a free relativistic particle of positive or
zero mass and arbitrary spin. Assume that at time $t=0$ the particle
is localized with probability 1 in a bounded region V . Then there is
a nonzero probability of finding the particle arbitrarily far away at
any later time.
Theorem 2. Let the operator $H$ be self-adjoint and bounded from below.
Let $\mathcal{O}$ be any operator satisfying $$0\le \mathcal{O} \le \mathrm{const.}$$ Let
$\psi_0$ be any vector and define $$\psi_t \equiv \mathrm{e}^{-\mathrm{i}Ht}\psi_0.$$ Then one of the following two
alternatives holds. (i) $\left<\psi_t,\mathcal{O}\psi_t\right>\not=0$ for almost
all $t$ (and the set of such t's is dense and open) (ii)
$\left<\psi_t,\mathcal{O}\psi_t\right>\equiv 0$ for all $t$.
Exactly how to understand Hegerfeldt's theorem is another question. It seems almost as if it isn't mentioned because it's so inconvenient (the second theorem, in particular, has a rather simple statement with rather general conditions), but a lot depends on how we define local and nonlocal.
I usually take Hegerfeldt's theorem to be a non-relativistic cognate of the Reeh-Schlieder theorem in axiomatic QFT, although that's perhaps heterodox, where microcausality is close to the only definition of local. Microcausality is one of the axioms that leads to the Reeh-Schlieder theorem, so, no nonlocality.