Could I say "pasta i szczoteczka do zębów"? Also, are these two expressions sometimes reduced to just "past" & "szczoteczka" in spoken language? (So is the "do zębów" part occasionally dropped?)
yes to both. as long as it is in circumstances that it's clear it is not other kind of szczoteczka (little brush) and pasta.
Wow! The correct answer! Signs of progress at last.
Is it possible "Pasta/szczoteczka _dla zębów" ?
I could see some sense in it, but that's just not what we say.
I can imagine someone saying that "ta pasta jest dobra dla zębów", "is good for the teeth". That's a bit of a different usage, though.