I'm sure there's a web-page somewhere that'll tell you for certain, but I'd be very surprised if 'pity' didn't come first, with the 'Pete' version coined later as a secular equivalent.
PS Yes - they can be used interchangeably, though I'd guess that the 'Pete' version was more common. I guess 'for pity's sake' might sound a bit old-fashioned - perhaps more appropriate for when something really painful/dangerous/life-threatening is happening:
'For Pete's sake, I've been holding on for half-an-hour! When can I get to speak to a human being?'
'For pity's sake, leave the children - take me instead.'