Could you show your entire screen with the layers panel open? Also capture your image size dialog box. (Image>Image Size...)
I want to find out why your image is that pixelated. I assume it is a low resolution issue, but I hate assuming.
This image is a good example to show what alising is. The edge your having an issue with is called alising. The black line which looks a bit blurred is called anti-alising. some commands have a check box for antialising and this image shows what that does.
Anyway, back to your issue, I will wait until I see more.
Yes. Like Bruce says.
Magic wand is prone to all sorts issues if used in this way. Refine edge will each smoothly into the AA, but I wouldn't dream of filling the spaces created with the MW. Much better to use a new layer underneath, and fill that, using a selection to constrain the outline if required.
OK, your pixel dimentions is high enough. For the two circles, I recommend that you use shapes instead of pixels when creating them. This will produce a better quality circle. It will also make it much easier to change its color.
When you create a selection it tends to be a hard edge. In the selection menu you will find a feather command. You can also use refine edge which will be a more visual approach. The feather will blend the edges.