Na temat jego losów po 1655 roku istnieje wiele niejasnych i wzajemnie sprzecznych informacji. Według staroobrzędowców miał być on później przewieziony pod ścisły nadzór do monasteru św. Warłaama Chutyńskiego w Nowogrodzie i tam zabity. Według innych wersji powstałych w kręgu staroobrzędowców rosyjskich miał zostać szaleńcem bożym. Wówczas Nikon, dowiedziawszy się o tym, nasłać miał na niego najemnych morderców. 3 kwietnia (według starego stylu – 16 kwietnia) 1656 roku biskup Paweł Kołomieński miał być spalony na stosie. Zdaniem historyka S. Łobaczewa okoliczności śmierci Pawła nie mogą zostać jednoznacznie rozstrzygnięte, jednak bezpośrednie zainspirowanie przez Nikona jego zabójstwa jest mało prawdopodobne. Paweł zmarł bowiem jeszcze przed rozpoczęciem masowych, popieranych przez władze świeckie prześladowań staoobrzędowców. Oficjalna wersja śmierci biskupa głosiła, że jeszcze w monasterze Paleostrowskim doznał pomieszania zmysłów, uciekł do lasu i utonął w rzece lub został pożarty przez zwierzęta.
Nie ulega jednak wątpliwości, że wkrótce po soborze w 1654 roku już nie żył. Nie zdążył ani wyświęcić kapłanów staroobrzędowych, ani nikomu przekazać sakry biskupiej.