Is your Selection feathered? It should have been set in the Options bar to zero.
Have you considered the Quick Selection tool which is more precise than the Magic Wand.,.
Have you considered making an Alpha channel of one of the color channels and increasing its contrast to create the basis for the mask.
If you're trying to replace a completely blown out sky with a pretty blue one, it's going to take a fair amount of artistry to make it look convincing. Depending on how blown out the sky is there's going to be some amount of 'leak', where the highlights creep onto the skyline (skyline being anywhere the sky interfaces with the foreground/background, be it buildings, trees, hair, etc). And the more detailed the skyline, such as in hair and tree leaves, the more difficult it'll be.
First, I'd recommend doing it in multiple layers. Don't try to fix it in one step, it won't look good. Several layers trying to mask in the new sky, adjust the highlights, etc. Multiple layers of small changes is the secret to realistic compositing.
Second, I'd start with using Select Color Range, not the magic wand.
If it's a really detailed skyline, I'd use channels and "burn" to try to make a selection. You can search tutorials on YouTube. The idea is that you find the channel with the most contrast, then burn/dodge/curves for even more contrast, then make your selection.
Beyond that is where the 'art' comes in. I'd probably add a hue adjustment layer, with colorize on, and try to color the blown out sky a light blue. Then I'd invert my mask and try to lightly paint in some blue highlights around the halo area. I'd probably even add a blank layer and literally paint in some blue - soft brush, very low opacity and fill - to even it out a bit. Again, small steps.
I'd also consider lowering the opacity/saturation of the sky you're adding in. Don't try to take it from a completely blown out sky to a perfectly blue one, it's just not going to work. Lighten it up a bit. And lighten it up more at the horizon. Something people usually don't do when replacing skies, and it's always obvious. The sky should be lighter at the horizon.
Finally, I'd get some more blue into the foreground/background. If there was a blue sky then the rest of the photo would reflect this to some bit. Your reflections are going to be all white because you have a white sky. I'd start with a color balance layer to add a bit more blue and warmth. But I'd also paint in some highlights: Sample some colors from the sky, and on a blank layer I would paint in some blue onto the foreground/background. Change your blending mode to something like soft light. Then, in the layer properties there's two sliders for "Blend If". On the lower one (for the underlying layer), hold down "Alt" and move the slider from the left towards the right. You're changing where your blue modifications apply, and since they're not going to apply in the shadows as much as the reflected highlights, I'd move them out of the shadows. Play around with it till it looks right. Making your adjustments not apply equally to all parts of the photo will really help it look more realistic.
The answer was to use the Quick Selection tool rather than the Magic Wand.
Apparently the halo was the result of the inaccurate selection made with the Magic Wand. The halo appears to have been the unselected area looking like a halo. As a result, the Refine Edge function would have little effect.