Ils sont partis en vacances il y a deux jours.
Ils sont partis en vacances depuis deux jours.
Which one of these sentences is correct and if the first one is correct, can "il y a deux jours" be used with any tense or just with the passé composé?
Both sentences are correct and convey basically the same meaning. The first one insists a bit more on the day the people left, the second on the length of the period people have not been there. Note that in French in this particular case you could also say:
Ils sont partis avant-hier.
This one, as your first example, insists on the day the people left. I mention this sentence because I can't think of a word for "avant-hier" in English so I guessed it might interest you.
To answer hour second question, any past tense would fit:
Ils partirent il y a 2 jours
Ils partaient il y a 2 jours
Note that it's not the case, from where I see it, for your second sentence. "Ils partirent depuis 2 jours" is not correct, and "ils partaient depuis 2 jours" would mean it took them 2 days to leave, which technically is not correct bit still can be used to express the idea that people actually don't really want to leave and/or are slow to do it.