As mentioned in the description text for the replacement character setting: After changing the replacement character, you need to rebuild Page URLs - AdminCP > VaultWiki > Wiki URL Manager > Rebuild Page URLs. I suspect you have done this already, since you're not complaining that pages are missing.
This fixes most issues, but doesn't fix saved category links or BB-Code links. There's really no way of doing this aside from saving the articles again. You might be able to fix them all at once with the Legacy Code Conversion process, but first you would need to create your own legacy tag in vault/class/bbcode/legacy/mediawiki.php that would affect all your articles - maybe have it do something simple like place a COMMENT tag at the beginning of all articles. It needs to change something, because if no changes are detected, the article won't bother generating a new revision.
Another way to avoid this issue in the future is to edit the Category pages before changing the replacement character. Once you edit the Category page, it will generate a Category ID number, rather than relying on how other articles have entered its name.
This will not be a problem in VaultWiki 4 because you can no longer add Category tags for Categories that don't exist. Adding the tag also creates the Category if you have permission; if you don't, you can't add the tag.