Franco had asserted that Tony didn't do dirty work like killing people, but Paolo wasn't going to take Franco's word for it. He wanted to get out of Tony's office as fast as possible, with the gun if necessary, and do some serious thinking.
Paolo had no problem with the killing bit, he'd already proved that, although Tony didn't know, but he did have a problem devising how to get Flaherty alone without arousing suspicion and getting himself either killed, or tortured or, if successful, arrested.
Luckily though, he knew how to get to Flaherty's girlfriend. Paolo had been there!