You seem to be a technically capable person, so I think you can understand what follows.
PAF can use two different kinds of media links: 1. RELATIVE LINKS give the media locations relative to the location of the PAF data file. 2. ABSOLUTE LINKS give the media locations as a full "file spec" starting with the drive they are located on.
I find relative links better because they still work even if you move the media to a different location (i.e. folder or drive or computer) To use relative links the media should be in the same folder as the PAF data file or beside it.
Now back to your main question: If you look at a gedcom file, a relative link looks like this: 2 FILE for-PAFill.jpg i.e. the image file "bill.jpg" is in the folder entitled "for-PAF" located beside the PAF data file using this link. If I look in that folder on my computer I will see a file called "Current Genealogy.paf" and a closed folder called "for-PAF".
I think the first step is copying your media to the right location relative to the PAF data file.
Then create a media link to one person and export everything as a new gedcom.
Open the gedcom in a text editor, and locate the link you just created.
Now do a global search and replace on the stem of the other media paths to make them match the stem of the link you just created. e.g. if the media path says 2 FILE c:My genealogyfor-PAFill.jpg you will replace c:My genealogy everywhere in your gedcom file, so that 2 FILE c:My genealogyfor-PAFDorothy Ing.jpg becomes 2 FILE for-PAFDorothy Ing.jpg and so forth.
Create a new PAF file with a NEW name and import your modified gedcom.
See if the links NOW show the correct images.
I hope it works. If not, please post the gedcom code for the new media link you just created, as well as the gedcom code for one of your old links that isn't working. I try to check this forum every week or two.
If you have your media scattered across multiple folders, life becomes more complicated. (Hence the suggestion to copy them all to the same folder)
Experimenting with PAF's own Global Search and Replace might produce the results you want. But you will probably need to check a gedcom file to find the path for the media files.