Biskup 23 maja 1758 został wyświęcony na biskupa tobolskiego i syberyjskiego i natychmiast podniesiony do godności metropolity. Do Tobolska przybył w listopadzie tego samego roku. Jego działalność w nowej eparchii ogniskowała się wokół prowadzenia misji wśród staroobrzędowców i rdzennych, pogańskich ludów Syberii. Badacze nie są zgodni w ocenie jego polityki wobec starowierców. Według niektórych metropolita Paweł, podobnie jak jego poprzednicy, w pełnej współpracy z władzami świeckimi organizował przeciwko staroobrzędowcom ekspedycje karne. Inni badacze przypisują mu jedynie organizowanie komisji odpowiedzialnych za poszukiwanie tych starowierców, którzy wbrew prawu nie deklarowali otwarcie swojego wyznania, lecz podawali się za prawosławnych.
W 1761 położył kamień węgielny pod budowę murowanego soboru katedralnego w TobolskuA. Nizowskij, Samyje znamienityje monastyri i chramy Rossii, Wecze, Moskwa 2000, , s. 435.