A nível de banco, e só pros telefones de Minas, da pra fazer a seguinte gambssolução:
UPDATE telefone
SET telefone = ( Replace (telefone, '(31)', '(31)9') )
Assumindo, é claro, que o campo telefone
seja uma string, e que todos os telefones tenham o mesmo formato. Ah, e que o campo se chame telefone
mesmo.