Revolt risk is affected by several factors, including religion (if you hold the cursor over the revolt risk in the province information window, you will get a dropdown box of these factors). As tolerance for a particular religion increases, the religious revolt factor for provinces of those religions becomes more negative (the exact revolt factor differs across religions). Since you cannot specify tolerance for paganism, the religious factor provides less of a negative effect on revolt risk than for religions that re fully tolerated and so pagan provinces are more revolt-prone. However, at +3 stability, they will never revolt, unless there is war-weariness or a random event.