The gray sky is actually going to make luminance keying easier. One thing I would suggest is, using a 2-step process: make a separate layer of the track and push the brightness and contrast settings to make the sky as even white or gray as possible, and don’t worry that it’s spoiling the quality of the rest of the shot. All you want to get out of this layer is a clean matte.
Then you extract that matte by inverting it, and add it back to a “normal” layer of the tulips pass, and now with those two tracks wedded together, you can key in a bare blue gradient in only the spots where sky would have shown thru. To make that sky better, yes, you will have to add a tracker, then a layer with clues and blue sky.
Some folks will do this in a 3-d comp so they have more control of the angles of that sky shot.