Nobody actually thinks of heathen gods any more when talking about weekdays, and even at a time when these were a bit more recognisable, practical concerns must have been important.
Mittwoch is an immensely practical term. It is both descriptive and shorter than the alternative. If anyone had actually worshipped Wodan on Wednesdays, things might have turned out differently, but if German Wikipedia (see Veredomon's helpful answer) is correct, the connection always was purely conventional in Germanic languages since it was the translation of a Latin convention that came from Babylonian.
Something similar is happening with Saturday in German right now. This day is still called Zaterdag in Dutch, but the connection to Saturn has long been completely lost in German. In the North it is quite logically called Sonnabend = Sun[day's]eve. In the South it is called Samstag, a term derived from sambaton, a Greek variant of sabbaton (obviously from Shabbat and related to English sabbath). Samstag is slowly winning over Sonnabend (i.e. the border is moving northward). Apparently, being one syllable shorter is more important than being descriptive. I know it is to me, but then I grew up in the South anyway... (Samstag is not descriptive because the derivation from Shabbat is obscure. By the way, a perfectly analogous phenomenon is Southern Orange replacing Northern Apfelsine.)
I believe Sabbat never had a chance to become the standard word for Saturday because in German (unlike Yiddish, of course) it's ambiguous. It can stand for Shabbat and imply Jewish observances, or it can stand for Sunday and imply Christian observances. (References to Shabbat in everyday German will normally be understood to have a Jewish context. References in a Christian setting or related to the Christian version of the Hebrew Bible are understood as Sunday.)
I believe the shift of Christian observances from Saturday to Sunday happened because Christianity is really a somewhat syncretic religion that evolved in a period of close contact between the Jewish sect founded by Jesus (one of many messiahs in his time) and the Mithras cult, an originally Babylonian religion immensely popular among Roman soldiers for some time. There are remains of Mithras temples in Germany.
Digression: Mithras was a personification of the sun. He held a Last Supper with twelve of his disciples before dying and later rising from the dead (as the sun always does). The Mithras cult baptised by submerging into water and sprinkling with bull's blood. Quite logically, the Mithras cult held its weakly celebrations on Sunday. It also had four yearly celebrations, two of which are related to Christmas and Easter. Appropriately for a soldiers' religion, the Mithras cult was only open to men, and Mithras sacrificed a bull rather than himself.