I have been asking me this question for a long time. What do birds and bees together have to do with reproduction? The only interaction they have is that some birds eat bees and that a bird can be stung by a bee. Now in my native German, the corresponding expression is “Bienchen und Blümchen”, “bees and flowers”. That makes sense, because you can teach kids about the concept of reproduction by telling them how bees pollinate flowers, and then you can take another step to explain how humans do it. What am I missing?
The implication is that there are two parts to the explanation: bees pollinating flowers (as you suggest) and the bird part presumably introduces the concept of fertilizing an egg that takes time before hatching.
Ah, I see. Seems like we Germans just skip the step with the eggs. 
Children will often and readily observe birds and eggs in nests as well as witnessing the bees and the flowers. Unless they live on a farm, or have a lot of cats or something, they are less likely to see live animal birth or mammals fornicating.
By the way, I’m pretty sure I’ve seen cartoons and comedians humourously playing on the idea of a romantic relationship between a bird and bee.
Wikipedia has a pretty good article on it, actually.
I can think of one contributing factor…
Now I have that song stuck in my head.
Hence the tale of a prim and proper Victorian vicar encountering a young girl driving a cow down a country lane. When he hears her explain that the cow is going to the bull in the next field, he says “But shouldn’t your father do that!” and gets the reply “Oh no, sir, it has to be the bull”.