The adjective paganus is derived from pagus and seems to originally mean roughly "belonging to a village". According to the L&S entry the sense "non-military" is also classically attested. In Christian use the word means "pagan". To what extent is this meaning a Christian invention? Did the adjective paganus mean any kind of non-believer or something similar enough before the advent of Christianity?
It could also be that the original Christian meaning of the adjective was different from how we understand "pagan" today, and the change occurred within Christian use. However, there seems to be a sharp contrast between the Christian meaning and the pre-Christian one, judging by the attestations I recall seeing. Perhaps intermediate examples of some kind would help bridge the gap between the two.