I had the same problem with Mail in macOS 12.x to 13.1 not saving signature edits and not being able to delete them. It was rather annoying to have to edit the signatures each time I sent an email and I was very close to going with a third party application. A case opened with Apple that went to their engineering came back with a response asking me to do a deep audit of my system which did not fix the issue.
However, I found a fix on reddit.com that may be helpful. It seems that Mail and its data in the iCloud Drive (the private settings data you can't directly access) needs to be unlinked (at least for me).
The fix: (macOS 13.1)
System Settings
Apple ID pane (right under search)
iCloud
iCloud Drive (I have mine on)
Apps Syncing to iCloud Drive -> Options
Documents
Uncheck Mail
Done
My signatures work just as expected with this off. In testing I turned it back on and the abnormal behavior reoccurred.
I don't know what consequences there are for having this unchecked, but at this point not having to edit the signatures every email makes up for this unknown.
Hope this helps.