The location (file) of a bookmark is in literal (string) form in the bookmark data, which is in variable bookmark-list and which is saved in your bookmark file.
You have these options, to change the file name of one or more bookmarks:
You can use command bmkp-edit-bookmark-name-and-location, which is bound to C-x p r globally. (A similar command is bound to r in the bookmark-list display.) With no prefix arg you are prompted for a new bookmark name (just hit RET for the same name) and a new bookmark location (file). With a prefix arg an editing buffer opens for the full bookmark record (what you see in the bookmark file).
You can use command bmkp-edit-bookmark-record, which is bound to C-x p E globally. (A similar command is bound to e in the bookmark-list display.) This is like C-u C-x p r: An editing buffer opens for the full bookmark record.
In the bookmark-list display (buffer *Bookmark List*), you can use command bmkp-bmenu-relocate-marked, which is bound to M-R. It relocates the target files of all (visible) bookmarks that are marked >.
You are prompted for the relocation target directory. Omitted bookmarks are excluded, by default (so you can hide some bookmarks from this operation without unmarking them). With a prefix arg, any omitted bookmarks that are marked are included.
In the bookmark-list display (buffer *Bookmark List*), you can use command bmkp-bmenu-edit-marked, which is bound to E, to edit the full bookmark records of the bookmarks that are marked >. An editing buffer opens for all of the full bookmark records together. Omitted bookmarks are excluded, by default. With a negative prefix arg, any omitted bookmarks that are marked are included. With a non-negative prefix arg, the edit buffer includes all bookmarks.
You can open your bookmark file as any file, and edit the text. You can use query-replace etc. However, it is probably a better idea to use C-u E in the bookmark list -- see previous (but be aware that C-u E works with the current bookmark-list, not the bookmark file, which is the last-saved bookmark-list).
There might be other possibilities, that I'm not thinking of at the moment. Use C-h m in the bookmark-list display for more information. Or check the Bookmark+ menu in the bookmark-list display. Or check the Bookmarks menu anywhere (under Edit in vanilla Emacs). Or use apropos-command...