Introduce a new landscape and colour match the scene
Open your start image. With your chosen selection tool, you want to make a rough selection of the sky area (we used the Lasso tool); it only has to be rough, as we’ll tidy it up in a minute. When you have a selection, go to Layer>Layer Mask>Hide Selection to add a mask.
Select the mask thumbnail and then choose the Brush tool. Make sure that the Foreground and Background colours are set to default black and white, then paint black to hide and white to reveal. Tidy up the mask so that none of the sky is visible.
Open your sky image. Go to Edit>Select All and then Edit>Copy. Go back into your start image and then Edit>Paste. This will bring in your sky on a new layer. Move the whole layer below the other layer so that the sky sits in the space create by the mask.
Tick Show Transform Controls in the Options bar. Hold down Shift and drag the corner handles to enlarge the sky to fill the space. Hoever over the bottom-right corenr handle until a rotation arrow appears. Drag to twist the sky to match the perspective.
Hold down Cmd/Ctrl and click on the layers mask thumbnail, which will select the area. Add a Colour Balance adjustment layer with the mask attached to the isolated layer. Move the slider towards Magenta and a little Red to match the sky colouring.