The problem is that the sky in the original picture isn’t uniformly blue or grey. So you either remove the sky and replace with a single colour (looks wrong), add a sky from somewhere else (can look wrong re shadows etc. - agreed) or faff around trying to find a sky that matches the sky already there and use the clone and smudge tools to try and blend it in, with varying degrees of success.
Or Leave the missing portion blank or a bright colour with a logo on it. 