Since the invention of the laser in the 60s, one of the most fundamental communication channels has been the free-space optical channel. For this type of channel, a number of effects generally need to be considered, including diffraction, refraction, atmospheric extinction, pointing errors and, most importantly, turbulence. Because of all these adverse features, the free-space channel is more difficult to study than a stable fiber-based link. For the same reasons, only recently it has been possible to establish the ultimate performances achievable in quantum communications via free-space channels. Differently from previous literature, mainly focused on the regime of weak turbulence, this work considers the free-space optical channel in the more challenging regime of moderate-to-strong turbulence. This regime may occur in long-distance free-space links on the ground, in uplink to high-altitude platform systems (HAPS) and, more interestingly, in downlink from near-horizon satellites. In such a regime we rigorously investigate ultimate limits for quantum communications and show that composable keys can be extracted using continuous variable quantum key distribution. In particular, we apply our results to downlink from satellites at large zenith angles, for which not only turbulence is strong but also refraction causes non-trivial effects in terms of trajectory elongation.