This might be a long shot but check whether you have all the latest PS updates as well as the latest Mac updates.
A while back ( about a year or more ago) after I had downloaded some updates , I was getting just those bandings like in your sky. Instead of having a smooth transition in the color of the skin of the person in my image, there was a blocky banding of the tones, like in your sky.
Shortly after, PS issued another update that fixed it. Not sure what it was but it was weird in that no one knew anything about it except I had gotten an email from one of my printing materials suppliers telling us about the problem.
I was only printing on the Enhanced matte paper so I don't know if it was on only that.
You might have reloaded an older version or something, who knows... stranger things have happened, eh?