You are right that there are two effects at play here.
Firstly, suppose that we turn relativity off --- suppose that we consider our universe to be Newtonian, with a finite speed of light propagation. It would indeed be the case that if an observer A were moving relative to another observer B, and emitting a light signal towards B, then the rate at which the signal arrived at B would be different to that at which it was emitted. This is the plain old Doppler effect, just the same as the effect experienced when listening to an ambulance moving towards or away from you. If the signal emitted by A was the light from her clock face, then indeed observer B would see the clock tick at a different rate.
But would she see it tick more quickly or more slowly? Now that depends on whether observer A were moving towards or away from observer B. If A were moving towards B, B would see the clock tick more quickly, just as you hear the ambulance siren at a higher pitch if it is moving towards you. Likewise, if A were moving away from B, B would see the clock tick more slowly, just as you hear the ambulance siren at a lower pitch if it is moving away from you. Of course, for speeds small compared to the speed of light, this effect would be very small.
Now suppose we turn relativity on. A new effect comes into play --- one much more profound and weird. The (relativistic) phenomenon of time dilation would entail that, according to B, the clock belonging to observer A runs intrinsically more slowly. It's not that she merely sees the the clock tick more slowly, it's that time itself has slowed down aboard A's spaceship, according to B. What this means is that if B were to measure the rate of arrival of signals from A and then do some maths to undo the Doppler effect, such that the resulting quantity obtained were the rate of emission of the signal, she would find the rate to be less than that at which A would say she emitted the signal. Which is pretty nutty.
So what is the combined effect? Well, we can see immediately that they won't cancel out in all cases by considering observer A to be moving away from observer B. Then time dilation and the Doppler effect combine, such that observer B sees the clock aboard A's ship running particularly slowly. The correct formula (I won't give a derivation here, but you can find many on the web, e.g. on Wikipedia) turns out, in fact, to be
$$ f_O = f_E \sqrt{\frac{1-\beta}{1+\beta}} \,,\qquad \beta = v/c\,,$$
where $f_E$ is the emitted frequency and $f_O$ the observed frequency. For all positive velocities, which in this case corresponds to observer A moving away from observer B, the top of the fraction is smaller than the bottom, and so the observed frequency is less than the emitted frequency. Likewise, for all negative velocities, which in this case corresponds to observer A moving towards observer B, the top of the fraction is larger than the bottom, and so the observed frequency is greater than the emitted frequency.
Qualitatively, then, the two effects combined are no different from the Doppler effect by itself. The only circumstance under which the two effects 'cancel out' is when the observers' relative velocity is zero, and in that case the two effects are individually zero! Whilst the Doppler effect results in an increased rate for $\beta < 0$ and a decreased rate for $\beta >0$, the phenomenon of time dilation always acts to slow the rate down. Then it just happens to be the case that for no choice of relative velocity can time dilation slow the rate down quite enough to counteract an increased rate due to the Doppler effect.
I've plotted the square root in the above formula below:
You can hopefully see that this function is always greater than 1 for $\beta$ less than zero, and always less than 1 for $\beta$ greater than zero. Hope this helps!
Best Answer
Nope, the "$c$" in the Lorentz Transformations doesn't just apply to the speed of propagation of information in a medium, though I understand why you might think of it that way. Instead, the Lorentz Transformations are fundamental to the structure of space and time itself. In particular, they imply that the speed of light $c$ is frame independent: all inertial observers will agree on this quantity.
Such an argument cannot hold for the speed of sound in a medium, which is not something fundamental, but which depends on properties of the medium itself like its density and pressure. Indeed, objects can (and frequently do) travel faster than the speed of sound in a medium. Furthermore, it should be clear that if you consider just the bats moving in air, they don't even satisfy the basic criterion for relativity: for example, the Doppler Effect for sound clearly distinguishes cases where the "source" is really moving and where the "observer" is really moving (with respect to the ambient medium).
The big result of special relativity is that there is one -- and only one -- frame independent speed, and that is $c$, the speed at which light happens to travel. It makes no physical sense to speak of a speed greater than this value. The speed limit of 343 m/s in your problem, however, is a biological limit. If the bats in your problem were replaced by fighter jets, they would certainly be able to move faster than the speed of sound. So I see no reason to draw a parallel. In other words, you don't need to teach the bats Special Relativity: good old-fashioned Newtonian mechanics should work fine.