ВайлдКэт довольно удачно упомянула перевод слова как "деревенщина". Именно в деревнях люди наиболее долго сопротивлялись христианству и поклонялись своим богам. Поэтому нехристианскую религию начали называть деревенской. То-есть, паганской.
Слово же "язычник" славянского происхождения и означает "иноверец". Так на Руси некогда называли христиан. Позже, когда христианство утвердилось на Руси, иноверцами (язычниками) начали называть нехристиан. Не только тех, кто верил в Перуна, но и мусульман и иудеев.