It would be helpful to know exactly which tool you used to tweak the sky and to see how it looked before. The histogram of you sky looks like it has been posterized, ie. jumping values, and then blurred to fill up the gaps. the causes for this can be working in a 8bit image space, doing multiple operations that should have made decimal values but then rounded to nearest integer, or the program using LUTs without doing interpolation of floating point values when looking up a decimal value, e.g. bilinear LUT lookup interpolation.
Here is an example of sky enhancement that introduces posterization, and then blurred. You see a smooth normal distribution in the first (original) and then peaks in the middle (posterized) and the last is kinda filled up with a shovel, but you see traces of the peaks:
Now look at your sky histogram. It has peaks with filled gaps. The standard deviation is very broad because you sky is a large gradient compared to my sky. Funny thing is that the blue is very narrow - your operation must have compressed the blue band while spreading the green and red:
I have recently taken an image with a similar sky as yours and my blue channel is not so compressed and the histogram doesn't have to many peaks and you don't see banding. I tweaked the curves and blues etc. keeping the 14bit raw pixels and working in 16bit mode, and didn't even use any "blur". (My sky histogram on top and yours as "reference":
So to answer your question, is there a better way to do it: Make sure you keep the number of bits your camera supports (12-14) by processing in 16bit mode. As I understand it PS Elements has limited 16bit support, but the curves tool would work, so I suggest you pull down the sky luminance with it in 16bit mode (not after having converted to 8bit first).