I am working on cleaning up user defined variables in favor of a consistent naming convention. Since the Name/Unique key field is not editable, the only other option I can think of is to create a new variable, find all instances of the old variable and change to the new variable, and then delete the old variable. Is it possible to do a find/replace all instances?

No, there is no built in functionality for this as far as I know. Maybe the Api can do this, but I don't use it so I can't tell. You could export all settings, do a search replace in the xml, and then import back. That's a pretty scary operation !