pagan (n.)

c. 1400, perhaps mid-14c., "person of non-Christian or non-Jewish faith," from Late Latin paganus "pagan," in classical Latin "villager, rustic; civilian, non-combatant" noun use of adjective meaning "of the country, of a village," from pagus "country people; province, rural district," originally "district limited by markers," thus related to pangere "to fix, fasten," from PIE root *pag- "to fasten." As an adjective from early 15c.

The religious sense often was said in 19c. [e.g. Trench] to derive from conservative rural adherence to the old gods after the Christianization of Roman towns and cities; but the Latin word in this sense predates that period in Church history, and it is more likely derived from the use of paganus in Roman military jargon for "civilian, incompetent soldier," which Christians (Tertullian, c. 202; Augustine) picked up with the military imagery of the early Church (such as milites "soldier of Christ," etc.).

The English word was used later in a narrower sense of "one not a Christian, Jew, or Muslim." As "person of heathenish character or habits," by 1841. Applied to modern pantheists and nature-worshippers from 1908.

Pagan and heathen are primarily the same in meaning; but pagan is sometimes distinctively applied to those nations that, although worshiping false gods, are more cultivated, as the Greeks and Romans, and heathen to uncivilized idolaters, as the tribes of Africa. A Mohammedan is not counted a pagan much less a heathen. [Century Dictionary, 1897]

The English surname Paine, Payne, etc., appears by old records to be from Latin paganus, but whether in the sense "villager," "rustic," or "heathen" is disputed. It also was a common Christian name in 13c., "and was, no doubt, given without any thought of its meaning" ["Dictionary of English Surnames"].