Se ho ben capito il campo:

Nome contiene "CognomeNome: Rossi"

Quindi TUTTI i campi Nome sono composti allo stesso modo: "CognomeNome: + un cognome" una prima parte conosciuta di lunghezza fissa ed una seconda parte sconosciuta e di lunghezza variabile.

Dato questa premessa proverei fare cosi':

codice:
UPDATE tab
set nome = concat('CognomeNome: Paolo', substr(nome From 13))
where id = ......
Pero' sinceramente eviterei di scrivere in ogni record CognomeNome:
si tratta di un dato non significativo per il contenuto del campo nome, e' ripetuto vanamente, occupa spazio, complica ed appesantisce la ricerca, da un formato prefissato che deve essere gestito quando basterebbe semplicemente aggiungerlo al momento della stampa.

anyway ...