Looks like JPEG compression artifacts generated on image noise in the sky when someone used a fairly low quality JPEG compression setting.
You can probably mitigate it somewhat by selecting just the sky (e.g., with the Magic Wand Tool) then using the Filter - Noise - Reduce Noise function in Photoshop.
I tried this but it made no discernible difference to the image, I'm afraid. Any further thoughts?
If you are willing to put in the time you could try making a good mask for the sky, create a new layer with it, clone stamp out the edges, convert to a Smart Object, apply the mask as a Layer Mask, apply Gaussian Blur and Add Noise to the SO.
Clouds in the sky region would naturally suffer and ultimately it might still not be »good«.
But that’s a risk of working with damaged images.
I'd suggest that perhaps you didn't set the Reduce Noise settings to be aggressive enough.
Post an unrealized portion of the image if you'd like more specific info.