Every find/replace dialog including the replace dialog for making replaces in binary files respectively hex edit mode has a Help button. By pressing on this button the appropriate help page opens. There is a small table listing the special codes including ^r for carriage return, ^n for linefeed and ^p for carriage return plus linefeed. Those special characters can be used for a normal, non regular expression and an UltraEdit regular expression find/replace.
For Unix regular expression finds/replaces \r, \n and \p can be used as listed in a table on the linked page titled Regular Expressions (Legacy)
And for Perl regular expression finds/replaces \r, \n and \r\n or \x0D, \x0D and \x0D\x0A can be used as it is common for Perl regular expressions. The hexadecimal values can be specified also with lower case letters a-f.
However, there is a problem here as I found out on trying your search on a binary file. In the find/replace dialog for files opened in hex editing mode ^r, ^n and ^p are interpreted as strings to find and not as special character codes with just option Find ASCII enabled. With turning on additionally Regular Expressions (ASCII Only) to use the UltraEdit regular expression engine the codes ^p and ^t (horizontal tab) are working, but not ^r and ^n. It was really surprising for me to see this difference in behavior in find/replace on files opened in hex editing mode. Even the very old version 11.20b of UltraEdit show this behavior like UE v19.10. It looks like you are really the first user which makes simple text replaces with carriage return and linefeed included on a file opened in hex editing mode. I will report this issue by email to IDM.
But I can suggest a workaround for this problem.
Open additionally to the binary file a new file. With the new file being the active file, press Ctrl+R to open the standard replace dialog. Enter as search string ^rMSH and as replace string ^pMSH, uncheck all options except Match Case and select All Open Files. Then click on button Replace All. The replace you want to do is now done in the binary file.
Of course you can also use the Perl regular expression engine and use your find and replace strings. But by doing this I detected a second issue in UE v220.127.116.112. While in the still opened Replace dialog as well as on the status bar of the UltraEdit main window the correct number of replaces in all files (= the binary file) is shown, a popup window opens with Perl regular expression enabled letting me know that the search string was not found (in active file). This is definitely in this special case with running a Replace All on all open files with string not found in active file a misinformation. I will report this issue also by email to IDM support.
Another workaround would be to use Find - Replace in Files with entering in field In Files/Types the name of the binary file (completely or with using wildcards) and selecting in Directory the directory of the file. This type of replace works with all possible variants (none regex, UE regex, Unix regex and Perl regex).