This answer elaborates on my comment to David Z's answer. I think his definition of a wave equation is excessively broad, because it includes every translationally invariant PDE and every value of $v$. For simplicity, let's specialize to linear PDE's in one spatial dimension. A general order-$N$ such equation takes the form
$$\sum_{n=0}^N \sum_{\mu_1, \dots, \mu_n \in \{t, x\}} c_{\mu_1, \dots, \mu_n} \partial_{\mu_1} \dots \partial_{\mu_n}\, f(x, t) = 0.$$
To simplify the notation, we'll let $\{ \mu \}$ denote $\mu_1, \dots, \mu_n$, so that
$$\sum_{n=0}^N \sum_{\{\mu\}} c_{\{\mu\}} \partial_{\mu_1} \dots \partial_{\mu_n}\, f(x, t) = 0.$$
Let's make the ansatz that $f$ only depends on $\xi := x - v t$. Then $\partial_x f(\xi) = f'(\xi)$ and $\partial_t f(\xi) = -v\, f'(\xi)$. If we define $a_{\{\mu\}} \in \mathbb{N}$ to simply count the number of indices $\mu_i \in \{\mu\}$ that equal $t$, then the PDE becomes
$$\sum_{n=0}^N f^{(n)}(\xi) \sum_{\{\mu\}} c_{\{\mu\}} (-v)^{a_{\{\mu\}}} = 0.$$
Defining $c'_n := \sum \limits_{\{\mu\}} c_{\{\mu\}} (-v)^{a_{\{\mu\}}}$, we get the ordinary differential equation with constant coefficients
$$\sum_{n=0}^N c'_n\ f^{(n)}(\xi) = 0.$$
Now as usual, we can make the ansatz $f(\xi) = e^{i z \xi}$ and find that the differential equation is satisfied as long as $z$ is a root of the characteristic polynomial $\sum \limits_{n=0} c_n' (iz)^n$. So our completely arbitrary translationally invariant linear PDE will have "wave-like solutions" traveling at every possibly velocity!