That is why you better make the backup without the leading / , for example (cd / && tar cf - .) instead of tar cf - / .
But IMHO you can tell pax to make some modifications. RTFM:
What did you exactly try with the "-s" parameter, because it basically does what you want it to do? And what was (exactly!) the outcome of what you tried? As long as the only description of what went wrong is "didn't work" it is hard to understand and tell you what you should have done differently (apart from the general advice of reading the manual. I take it you did that but obviously you didn't completely understand what it said.).