While The Protagonist rescues Pierce from his nightmare simulation created by the Zin Empire, they end up going up against Paul who appears as a boss in the mission. The Protagonist takes control of the Steelport statue on Magarac Island and battles Paul by beating him, opening him up and throwing him onto where the statue stood, presumably killing him.
After rescuing Zimos, The Dominatrix orders Paul to terrorize the city. In order to kill Paul, the Saints created a space ship so they can go into Paul's mouth and destroying his brain. After destroying his brain, Paul spews out Saints Flow.
Paul originally appeared in a promotion for Enter The Dominatrix in early 2012, before the game was merged with Saints Row IV. He appeared in the Saints Row IV Reveal Trailer and the Independence Day Trailer.
Asha mentions Paul during the the mission "The Case of Mr. X" when she says "fighting a 50 foot soda can". This could mean that she was tasked to fight Paul but failed before The Protagonist rescues her.
When Kinzie mentions Paul to Pierce, he becomes instantly angry, which is unusual for his character.