On a purely etymological note, the word
pagan comes from
paganus (plural
pagani), old Latin for peasant or rural dweller, i.e. not a Roman, so probably invested in older beliefs. It might have been used pejoratively, in the divide of urbis and orbis (the City (Rome) and the world) at times, but it may also have been used as a shorthand by some.
Heathen is probably, according to Merriam Webster, a similar term, in that it most likely derives from a term for a rural person, or someone who lives on the heath (moorland, rough land with heather, etc.). On blasted heath to quote dear Will Shakespeare. Again, rather pejorative, and from a city-dweller's perspective. Typical toonser snobbishness.
Infidel, however, is much more assured in its disdain for the person. It might be used for one who is outside of a certain religion, but it really means not of the faithful, or faithless, or unfaithful. In that last, it's related to infidelity. It's the antonym of the Latin fidelis, loyal, trustworthy, faithful. To not be those things is more than to come from another part of the world or land, but is actually a stain on the character.
So, to return to Toby's original question, they may be used in similar circumstances by some writers, but they have different contexts. The first two are statements of otherness, but not
necessarily anything bad. I don't understand football supporters (of any team), even think they're a bit strange, but we can live and let live. The third word, though, if a definitive statement that the person is a bad 'un, not to be trusted, It should be noted that this could be completely untrue, but that's the power of words in creating a narrative. Repeat a lie about 'them' enough times, and eventually many of 'us' will believe it. Unfortunately.
I'm not going to add any more to this conversation, or I'll likely end up in things that we rightly don't discuss on Chrons (I wish we did sometimes but, having seen the trouble it caused, I'm glad we don't).