Why do snake (serpent) and bull often come together as symbols of deities?
The Celtic Cernunnos, the Greek Dionysus, the Slavic Veles and Vedic Shiva have snake and bull among their symbols.
Why do these two symbols tend to come together?
It looks to me as though these deities also share some other similarities. They tend to be somehow associated with the Moon, the underworld, fertility, and knowledge (magic).
Although, if we take other characteristic into account, we would probably replace Dionysus with Hermes. Hermes is not associated with the bull but he is associated with snakes, knowledge, and the underworld.
To make my point stronger, I would like to add that all four mentioned deities (Cernunnos, Dionysus, Veles and Shiva) are associated with fertility. Cernunnos and Shiva are both associated with deer or stag. Veles and Shiva are both gods of cattle.
Can you elaborate on the idea of replacing Dionysis with Hermes? Not sure where you're going with that.
@DukeZhou, of course I do not meant that Dionysis is "replaceable" by Hermes. Of course they are very different. What I mean, is that Hermes seems to fit better to the group consisting of Cernunnos, Veles and Shiva. For example Hermes is psychopomp like Cernunnos and Shiva. Veles seems also to have something with underworld.
@Roman Gotcha. Dionysus definitely has a strong fertility/rebirth connection, and he is slaughtered and consumed like kine or game. That said, I was just reading that the horns on the Mercury symbol represent the wings on his hat, but they sure look like horns to me, and he is associated with bovines in that he stole Apollo's cattle...
This is only a partial and working answer until I can look into Cerunnos, Veles, and Shiva.
My first inclination is that this is a case of the Texas sharpshooter fallacy. These four gods have associations with those two animals, and so you posit they must be a related. However, there's no telling when these gods developed these characteristics and whether they're primordial or just highlighting two accidental convergences.
Let's take a look at the Greek side, since I know that best.
First of all, snakes have long been a symbol of immortality. Think of the snake in the Garden of Eden or the Gilgamesh epic who snatch away immortality from Adam and Eve or Gilgamesh, respectively.
In the Iron Age, Dionysus developed a cult of immortality around him, one of the several savior cults around the Mediterranean. The most solid evidence comes the 400s, but it likely developed earlier. Multiple tablets attest to Dionysus' power to rescue souls from the Underworld. This could have given Dionysus his serpentine associations. (Cole, 338ff.)
As far as the bull goes, this is likely Mycenaean in origin and probably predates any the snake associations. Cattle are sacred to Dionyus at Cynathea in Arcadia, which has an unusual feast to him there (from Theoi):
(Pausanias, Description of Greece 8. 19. 2) "The most notable things here [at Kynathea, Arkadia] include a sanctuary of Dionysos, to whom they hold a feast in the winter, at which men smeared with grease take up from a herd of cattle a bull, whichever one the god suggest to them, and carry it to the sanctuary. This is the manner of their sacrifice."
He is also called "bull-faced" in the Orphic hymns, paralleling the epithets for Hera (cow-faced) and Athena (owl-faced, or possibly gray-eyed).
Also, I wouldn't write off Hermes right away. The earliest sources for Hermes after the Odyssey definitely tie him to cattle. In his Homeric Hymn, Hermes steals the cattle of Apollo and then lies about it. He was so clever at it, though, Zeus granted him a position on Olympus. The snake association is actually more tenuous, as the entwined serpents around his staff is rather late iconography, and perhaps comes from Hippocratic symbolism, which in turn developed from the Asclepius cult. (See Wikipedia for a good rundown of the evidence.)
While I haven't looked at the earlier gods, I do think this analysis should lead you to hesitate in positing whether the snake and the bull really do belong together.