There's an excellent article by Chris Durston that details the history of 'the Puritan war on Christmas' in 16th-17th century England (Durston 1985; also good is Pimlott 1960).
The 17th century version of the 'Christmas is pagan' meme is first and foremost an anti-Catholic idea. It begins with the perception that Christmas was a time for wanton revelry. In 1583 Philip Stubbes complained in his pamphlet Anatomie of abuses,
But specially in Christmas tyme there is nothing els vsed but cards, dice tables, masking, mumming, bowling & such like fooleries: And the reason is, they think they haue a commission and prerogatiue that time, to do what they lust, and to folow what vanitie they will. ... But the true celebratioĢ of the Feast of christmas is, to meditat (and as it were to rumiā£nat) vppon the incarnation and byrthe of Iesus Christ ...
Games, plays, and bowling? The horror!
By this date there was already a ban on Christmas celebrations in Presbyterian Scotland. The sentiment was tied up with anti-Catholicism. Here's a conversation between two Puritans of Amsterdam in Ben Jonson's play The alchemist (1610), Act III Scene III:
SUBTLE. And, then, the turning of this lawyer's pewter
To plate at Christmas --
ANANIAS. Christ-tide, I pray you.
SUBTLE. Yet, Ananias?
ANANIAS. I have done.
SUBTLE. Or changing
His parcel-gilt to massy gold. ...
Ananias' avoidance of the word 'mass', and the wordplay on 'mass' in the last line, are gibes about Puritan anti-Catholic sentiment. In the previous scene another Puritan, Tribulation, had asserted that if an evil person is against the Roman church, that makes them OK ('This heat of his may turn into a zeal, / And stand up for the beauteous discipline / Against the menstruous cloth and rag of Rome').
Subsequent decades saw a progressive increase in Puritan complaints about Christmas. It's in the 1630s that the anti-fun, anti-Catholic sentiment starts to get conflated with paganism -- the notion that a Catholic festival is pagan. In William Prynne's screed against the evils of the theatre, Histriomastix (1632), Christmas is spent in
amorous, mixed, voluptuous, un-Christian, that I say not, pagan dancing ... drinking, roaring, healthing, dicing, carding, masques and stage-plays ... better become the sacrifices of Bacchus, than the resurrection, the incarnation of our most blessed Saviour.
It's around this time that the idea is invented that Christmas customs are derived from Saturnalia. This gets repeated more and more as Puritanism rises.
In the 1640s things came to a head, partly thanks to the February 1642 proclamation that the last Wednesday of each month should be a day of solemn fasting. In 1642, this meant that the Feast of Holy Innocents (28 December) should be a fast day, prompting the Anglican churchman and orator Thomas Fuller to state in a sermon that day that
on this day a fast and feast do both justle together, and the question is which should take place in our affections.
Two years later in 1644, Christmas itself fell on the last Wednesday of the month. The parliamentary ordinance proclaiming the fast on 19 December 1644 recommended that the fast be kept especially because
it may call to remembrance our sins, and the sins of our forefathers who have turned this Feast, pretending the memory of Christ, into an extreme forgetfulness of him, by giving liberty to carnal and sensual delights.
This was essentially the beginning of the Puritan prohibition of Christmas. Starting the following year, all religious observance of Christmas was outlawed. Christmas 1647 saw active civil unrest, both for and against the observance of the festival. From then up until the end of the Protectorate in 1659, Christmas remained a tricky problem: on the one hand the prohibitions were obviously insane, and impossible to enforce strictly; on the other hand, any observance of the festival was potentially a gesture of support for the monarchy.
So there was active debate over Christmas in this period, and much of the debate was preoccupied with the origins of Christmas. Joseph Hemming's Certain queries touching the rise and observation of Christmas (1648) argued that
('Yule' was already synonymous with Christmas by this time: the name was used to disparage the festival by association with something that was supposedly pagan. In reality Yule started out as a season in the old Germanic calendar, and was only secondarily a festival, but that's another story.)
So Hemming equated Christmas with both popery and paganism, and popery and paganism with one another. I won't detail the debate coming from the other side, other than to point out that there was a debate: the Puritans weren't screaming into a void. For the Puritan side of things, Hemming was followed up by other pamphlets like Robert Skinner's Christs birth misse-timed (1648) and Thomas Mockett's Christmas, the Christians grand feast (1650), which made similar arguments. The charge of paganism is consistently just a side-dish to add weight to the charge of popery. Skinner, p. 7:
And thus all error cometh from Rome, that bitter Starre, Worme-wood, cast into the fountains of the Scriptures and Vniversities, to corrupt and bitter them, not to better them ...
Mockett's rant against Christmas is the most detailed. Pp. 6-7:
This change of Pagan idolatrous feasts into Christian, in honour of Christ, and the Saints, was made by some of the Ancients, when Christianity was spread among the Heathens, and many of them converted to the true faith, in hope, that by complying with them, in observing their festivall days but to Christian ends, they should the rather draw the Pagan Idolaters from Paganism to Christianity. Pope Telesphorus who began about the year of Christ 140 in the time of Antoninus the Emperours reign, was the first Authour we read of among the Romans, of the celebration of Christs Nativity, and on that day Saturns devil-feast was began, viz. December the 25 ...
All of these claims are spurious, but the one about Pope Telesphorus does actually have a documentary basis, spurious though it is: it comes from the report of Telesphorus' life in the Liber pontificalis, though it's no older than the 6th century. Later Mockett carries on and makes the equation 'popery = pagan' clearer (pp. 19-20):
And sure I am the observation of these Heathenish, Popish holy days, comes under some of these heads ...
The very name, with which the Pope and Papists have christened it Christ-mas, is enough to make all true Christians to abhorre the observation of it Christ-mas, because the Papists had on that day a peculiar Masse pretendly in honour of Christ, but to his great dishonour, it being a most detestable Masse of Idolatry, in divers perticulars, as these Protestant Divines writing against the Papists doctrines, do unanimously affirm ...
Actually I will mention just two tracts written on the other side, since they're also the earliest dateable references to the figure of 'Father Christmas': namely The arraignment conviction and imprisonment of Christmas (1645) by one 'Cissely Plum-Porridge', and The examination and tryall of Old Father Christmas (1658) by 'Josiah King', both obvious noms de plume (the biblical king Josiah was a monotheistic reformer).
{The above paragraph has been edited}
The Protectorate came to an end in 1659, but the same year, Massachusetts outlawed Christmas: the movement to conflate Catholicism with paganism didn't fully end, it just shifted around.
Part 2, below, is on the version of the 'Christmas is pagan' meme that arose in the late 1800s.