Everything I know about PMF I just learned by reading http://forum.doom9.org/showthread.php?t=142944
(short version for others reading PMF files are MPEG PS with an extra header of 0x800, H264 video and the PSP AT3 audio format, which I have never done more than convert into wave though that should not be an issue here). I am half shocked as most of the time if it is a video in a game and it is not RAD/bink, some WMV variant for MS stuff or something from the Ogg/Xiph stable you can barely even get it decoded give or take a handful of Japanese games using original MPEG.
First though there is basically no such thing as hardsubbing losslessly unless you also go to lossless for your new encode or happen to have black bars in the video you can stick the subs onto, the first of which is not that useful and the latter of which is unlikely. The drop will not be that bad though and depending upon how much you need subbed you might be able to cut that down a bit and stitch a stream back together.
Video editor. I am having a hard time finding a straight up encoder and/or muxer aimed at it let alone an editor and that rarely changes for the higher end paid video editors as such things seldom have great format support. However given the other information you should be able to go manual easily enough and you actually do not need a fancy editor so much as something that will take your subtitles and feed that and the video into an H264 encoder -- you are working on the PSP which for my money is probably the least hacked hackable console, certainly the least hacked for as long as hacks have been viable on it so you are not in for an easy time.
The hardest part is probably going to be sorting whatever that 800 long header is. With the MPEG program stream taking care of anything fancy as far as the AV setup and interleaving goes and your otherwise not changing anything in terms of stream length or anything it is probably (hopefully*) just going to be finding whatever values it might have for size which will probably change (hopefully for the smaller so you can just pad it out but who knows).
*many a time I have come up against the attitude of "of course I know better than MPEG how video works" or "writing libraries is hard, let us extract the info and add pointless extra header".