Forget the magic wand. Grab the Free Select (Lasso) tool, and draw a selection around the sky. You can make sure you get right to the edges by going outside the image boundary at the top, left and right. When it comes to the horizon, follow the line of trees very roughly but don't worry about being too precise. Now go to Select > Feather, enter 150 pixels and click OK. This will give you a soft, natural looking transition between the sky and foreground.

Now, it's always best to edit non-destructively. Because GIMP doesn't have Adjustment Layers like Photoshop, this means editing separate image layers. So, duplicate the background layer (there's an icon at the bottom of the layers palette to do just that). Then right click the new layer and click Add Layer Mask. Choose Selection and click OK. The area you had selected (i.e. the sky) is retained, and the foreground is masked out, so you are in fact looking at the foreground on the layer beneath.

Make sure you have selected the layer contents rather than the mask by click on the layer thumbnail icon (it should have a white border around it). You can now use the Levels or Curve tools (avoid Brightness/Contrast) to adjust the sky however you like. If you want to adjust the foreground, simply select the appropriate layer (duplicate the background layer again to retain a non-edited version) and adjust that.