Though this is a very late answer, I have had success with an add-in called RegEx Find/Replace to do exactly what you want. But I do not know of any built-in capability for this in Excel.
The add-in creates a button on the ribbon which launches a dialog box that looks very much like the Excel Find/Replace. Most of it works the same as well - you can search within a sheet or workbook, by columns or rows, match case, etc. (There is no format matching, though.)
Note, however, that the add-in uses regular expressions as implemented in VBScript and so works differently than the standard Excel Find/Replace. For example, your search string
_* would not work. It matches any cell with zero or more underscores, which is anything. For your example, I had success finding
_(\d+) and replacing with
'($1). (The apostrophe is just to prevent Excel from interpreting
(4) as a negative value.)
I am in no way affiliated with the website or developer - just found it through a web search. Also, I use Excel 2007 and cannot say whether this still works in later versions. I have used it successfully in both Windows 7 and Windows 10.
The RegEx Find/Replace add-in can be found at http://www.codedawn.com/excel-add-ins.php