Closely related to the verb is the noun fang "plunder, spoils". It also meant "an instrument for capturing or holding", and this led to it being used to refer to canine teeth, or the dangerous teeth of any animal.
It's from a nasalized form of Proto-Indo-European *paḱ-/*paǵ- "to fasten". This root became Latin pāgus "of or belonging to a country community, civilian, inhabitant of a country community" (from "boundary staked out on the ground"). pāgānus initially referred to someone who lived in the country. This apparently became post-classical Latin paganus "heathen".
There are three possible reasons why the sense of paganus developed into "heathen".
1) Heathens lived in the country.
2) paganus also meant "civilian" as opposed to "soldier". Since Christians considered themselves soldiers of Christ, they used the term for "civilian" for non-Christians.
3) paganus had an intermediary sense "outsider", as in someone outside the city, and this came to be applied to people outside the community.