Both 'leave' and 'depart' go with 'for'. The word 'for' refers to the direction or the purpose. When you are leaving your house to go to work, you say 'I'm leaving for work'. If a train is departing from the station with Paris as its destination, you say 'It's departing for Paris'. You wouldn't use 'to' in these situations.

I would say "leaving for ______ "

You hear the word depart mostly when you're traveling from one place to another using a bus / plane / ship etc therefore it sounds more formal Leave, you can say he's leaving out the door which is an idiom but you can't say he's departing out the door. As for the "to/for" you can use both. If I'm traveling I'd much rather say I'm simply "traveling to" rather than "departing to"