Paul is correct, as usual. I was going to suggest Greg Maxey's
Bookmark Tool. However, that only takes care of the renaming part.
If you know the original name of the bookmark and if the cross-references are all done in REF fields, you could display fields (Alt+F9) and use a Replace to change it. This is far from automatic.