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.