A general solution can be presented as
\begin{equation}
\int d^3 \vec k \Big[ g_1(\vec k)e^{i|v||\vec k|t-i\vec k\cdot \vec x}+g_2(\vec k)e^{-i|v||\vec k|t+i\vec k\cdot \vec x}\Big] \qquad (1)
\end{equation}
with arbitrary $g_1(k)$ and $g_2(k)$.
It follows from your formulas, after you express $\omega$ in terms of $k$. Two terms correspond to two ways of taking the square root. If you additionally require that the solution is real, then you need to impose
\begin{equation}
\Big(g_1(\vec k) \Big)^*=g_2(\vec k).
\end{equation}
In (1) the integral goes over spatial $k$ only. In principle, you can make it over all $k$ in space-time (I mean, including $\omega$). Then, as it is clear form what you wrote, you need to solve
\begin{equation}
g(\vec k,\omega)(\omega^2 - |v|^2 |\vec k|^2)=0.
\end{equation}
Its general solution is
\begin{equation}
g(\vec k,\omega) = f(\vec k,\omega) \delta(\omega^2 - |v|^2 |\vec k|^2), \qquad (2)
\end{equation}
where $\delta$ is the Dirac delta. Note that in (2) only values of $f(\vec k, \omega)$ at $\omega^2 - |v|^2 |\vec k|^2=0$ are relevant. Indeed, if we replace
\begin{equation}
f(\vec k,\omega)\to f(\vec k,\omega)+(\omega^2 - |v|^2 |\vec k|^2)\alpha (\vec k,\omega)
\end{equation}
with any $\alpha$, then (2) remains unchanged due to $\delta(x)x=0$. The above replacement allows to change values of $f$ arbitrarily everywhere away from $\omega^2 - |v|^2 |\vec k|^2=0$. Thus, only values of $f$ on $\omega^2 - |v|^2 |\vec k|^2=0$ actually contribute to (2).
The general solution than acquires the form
\begin{equation}
\int d^3\vec k d\omega f(\vec k,\omega) \delta(\omega^2 - |v|^2 |\vec k|^2) e^{-i\omega t + i\vec k\vec x}. \qquad (3)
\end{equation}
If you need a real solution, you need to impose
\begin{equation}
f(-\vec k,-\omega) = \Big( f(\vec k,\omega)\Big)^*.
\end{equation}
The solution in this form can be easily connected to (1) if one eliminates the $\omega$ integral using the delta function.
