The appropriate time to explain the religious beliefs depends entirely upon the level of exposure your children have to adherents of those particular faiths.
Quite honestly, I still do not fully understand the religious significance of Ramadan, apart from it being a period of fasting (thanks, Wikipedia!). Also note that Kwanzaa is, to my understanding, more of a cultural celebration than religious.
I understood Christmas from an early age simply because the vast majority of the people around me were Christian.
By contrast, most Christians I know today have only the faintest of concepts of what Channukah is about (most seem to assume that it is one of Judaism's most important celebrations, and that the gift giving is symbolic of something; in reality, Channukah's biggest claim to fame is that it happens to fall at roughly the same time as Christmas, and the gift giving is solely a concession to the gift giving component to Christmas).
You can start out with a thumbnail sketch of each holiday as soon as they become aware of the holiday, and then fill in more details as your child asks more questions. Let your children's curiosity be the driving factor in determining how much detail you provide. Just be aware that the more exposure they have to a holiday (e.g. seeing Christmas trees on sale everywhere, lights decorating houses, friends talking about what presents they asked for/received, friends saying they can't eat because of the holiday, etc.), the more questions they are likely to ask.