Hi partner,
Here are the steps.
1.You should use Xrmtool box, please download it and install these tools: "AutoNumber Manager","Bulk Data Updater","FetchXml Builder".
2.Update the new number format for your existing records in "AutoNumber Manager".

Select the solution you are working on and choose the number field, then set the format to C{SEQNUM:5} which represents C00001 format.
Click update.
3.Create a new temporary entity with a lookup field related to contact entity, and set the "new_name" as optional.(in default it is business required)
4.Create a number field for the new temporary entity in "AutoNumber Manager" tool.
5.Create a workflow based on "Contact" and trigger it when number field has been changed.
6.Add a condition to check if the number field already has data, then stop the workflow.
7.If not, add a create action to create new temporary record and set its lookup field to current contact.
8.Add an update action for contact and set its number field value as the temporary entity number value.
9.Use "Bulk Updater" tool to update the contacts you need and update the number field only.
After running all the steps above, I changed my existed numbers successfully.
For example, in my custom entity, the original number is "C00001", now I want to update them to "CCC-00001".
Before

After

You could also refer to this link for more details.
https://jonasr.app/2019/02/anm-existing/
Regards,
Leo