After much research, I have determined that it is just not possible to
combine wildcard characters with replace. They are very useful for searching,
but they don't help with the situation I detailed above.

For anyone that might be interested in how I resolved my issue, I basically
removed all non-numeric characters from my data, so that each of my phone
number cells was formatted as 5555551234. Then, I converted the text to
tables, using fixed width columns of 3 characters, 3 characters and four
characters. Then, in a fourth column, I entered the formula
=CONCATENATE("(",A1,") ",A2,"-",A3). I then copied and pasted the values of
this column io ntthe original column to replace it with the updated
formatting.

It was a bit of pain because I had to copy the formula into each cell in a
very long column (over 17,000 fields) but copying and pasting groups of cells
made this a very quick fix.

I'm sure there is a much neater way to do this programmatically, but my
skill level is very limited in those areas.