Thanks for pointing this out, I should have been more precise. I was referring to time invariant equations. You are right that this doesn't apply to the wave operator (which also does not commute with rotations in R^4). But in space only, yes polynomial means polynomial with constant coefficients.
The proof basically goes that commuting with translations implies immediately that L has constant coefficients. Then on the Fourier side applying L translates to multiplying by a polynomial, and commuting with rotations translates to the claim that that polynomial is rotation invariant. And every rotation invariant polynomial in several variables is p(|x|^2) for some polynomial p in on variable. Then on the spacial side p(|x|^2) translates to L = p(laplacian).
The proof basically goes that commuting with translations implies immediately that L has constant coefficients. Then on the Fourier side applying L translates to multiplying by a polynomial, and commuting with rotations translates to the claim that that polynomial is rotation invariant. And every rotation invariant polynomial in several variables is p(|x|^2) for some polynomial p in on variable. Then on the spacial side p(|x|^2) translates to L = p(laplacian).