Secondo me faresti prima a toglierlo il più da tutti i record e al limite metterlo solo in fase di visualizzazione. Comunque

codice:
update tabella set campo_cellulare = concat('+',campo_cellulare) 
where id < 579 and substring(campo_cellulare,1,1) != '+'
fatti prima il backup della tabella per sicurezza.