The last great pagan kingdom in Europe was that of Lithuania, which began its rise under Gedmyn in 1316 or so. Lithuania remained a pagan Kingdom until about 1387, when Jagiello, King of both Poland and Lithuania converted to Catholicism.
Tricky subject. There is no law in the SCA covering pagan personae specifically, except the one tenet that obvious trappings of any kind of religion should not be used. This shouldn't be a major issue for you as most early pagan religions were not proselytical.
Do a lot of reading. I (Del) cannot claim to be an authority on pagan cultures, in fact I know very little apart from what I wrote above. When you've done your research come back and fill this bit in, and correct and/or expand this article. Please. It's probably a complete shocker.