Users PNS and Dale contributed heavily towards answering a solution, but didn't actually answer the question which was "What is the frequency shift..."
I know now that I have to add speeds with the relativistic formula for speed addition when it comes to relativistic speeds, but I did not know to which Doppler equation I have to insert these speeds.
So here is what I've came up with:
Legend:
- $c_s$ - signal speed from my reference point
- $c_{c_0}$ - signal speed in medium
- $v_w$ - speed of medium (wind speed)
- $v_e$ - emittor speed
- $v_a$ - absorber speed
- $f_e$ - frequency emitted
- $f_a$ - frequency received by absorber
- speed of Emittor is positive when it is trying to approach the Absorber
- speed of Absorber is positive when it is trying to approach the Emmitor
- speed of the medium is positive when it s flowing from Emmitor to Absorber

The classical Doppler formula looks like this:
$$f_a=f_e {\frac{1-\frac{v_a}{c_s}}{1+\frac{v_e}{c_s}}}$$
Classical Doppler formula is usually used for sound, but it is also frequently used for radio-waves traveling through vacuum (although the equation is further simplified with the first order Taylor series).
If I also want to include the speed of wind relative to me, an outside observer, the formula looks like this:
$$f_a=f_e {\frac{1-\frac{v_a}{c_{s_0}+v_w}}{1+\frac{v_e}{c_{s_0}+v_w}}}$$
As long as $v_w$, $v_a$ and $v_e$ are are at non-relativistic speeds the formula is accurate enough. But it's not accurate anymore when one of those speeds approaches the relativistic speeds (such as $\frac{1}3$ the speed of light in vacuum).
So I thought I'd use the relativistic Doppler formula:
$$f_a=f_e \sqrt{\frac{1-\frac{\Delta v}{c_0}}{1+\frac{\Delta v}{c_0}}}$$
Where $\Delta v$ is simply $v_e+v_f$ when $v_e,v_f << c_0$ and
$\Delta v = \frac{v_e+v_f}{1+\frac{v_ev_f}{c_0^2}}$ otherwise.
The formulas would look like this
$$
f_a=f_e \sqrt{\frac{1-\frac{v_e+v_f}{c_0}}{1+\frac{v_e+v_f}{c_0}}},
f_a=f_e \sqrt{\frac{1-\frac{\frac{v_e+v_f}{1+\frac{v_ev_f}{c_0^2}}}{c_0}}{1+\frac{\frac{v_e+v_f}{1+\frac{v_ev_f}{c_0^2}}}{c_0}}}
$$
But how am I going to add the medium in it?
It is true, that if I just replace the $c_0$ with $c_s$, the accuracy of the relativistic Doppler formula increases, but lowering the $c_s$ in the relativistic formula brings another problem:
Relativistic Doppler formula is only accurate when all speeds are much smaller from the speed of light in the vacuum. And if I use the the $c_0 --> c_s$ hack, it's accuracy decreases as soon as any of the speeds come close to the speed of signal in the medium.
$v_e, v_a << c_s$ must hold to use this equation.
Because my original question was about signal traveling in water, where light travels 25% slower than in vacuum, neither the Classical nor the Relativistic Doppler are good enough approximates because both are contributing to the end result. So I have to somehow use both.
Luckily I've come about this article which describes the general Doppler for any speed derived from relativistic Minowski diagram. It is exact for any speed as long as they are such that they don't produce any shockwaves. If they do, the frequency becomes negative, and that can either mean that the Absorber is moving too fast from the Emmitor for the signal to even reach him or that the Emmitor is traveling so fast in the medium that he would reverse the signal (and overtake it).
The general Doppler formula from mathpages.com looks like this:
$$f_a=f_e {\frac{1-\frac{v_a}{c_s}}{1+\frac{v_e}{c_s}}\sqrt{\frac{1-\frac{v_e}c}{1+\frac{v_e}c}}}$$
All I have to do now is modify it in a way to incorporate the change of signal speed due to the medium moving (wind blowing).
For non-relativistic speeds and any speed of the signal in medium:
$$c_s = c_{s_0} + v_w$$
For any speeds, as long as they don't produce shockwaves:
$$c_s = \frac{c_{s_0} + v_w}{1+\frac{v_w v_{s_0}}{c_0^2}}$$
And I get the the most general formula:
$$f_a=f_e {\frac{1-\frac{v_a}{\frac{c_{s_0} + v_w}{1+\frac{v_w v_{s_0}}{c_0^2}}}}{1+\frac{v_e}{\frac{c_{s_0} + v_w}{1+\frac{v_w v_{s_0}}{c_0^2}}}}\sqrt{\frac{1-\frac{v_e}c}{1+\frac{v_e}c}}}$$
And because my question was about the frequency shift when both the observer and emitter are stationary, I enter zero for $v_e$ and $v_e$ and I get:
$$f_a=f_e {\frac{1-0}{1+0}\sqrt{\frac{1-0}{1+0}}} = f_e$$
There is no Doppler effect when the speeds of emittor and absorber are the same.

URL for Desmos graph to play with