UPDATE TableName
SET ID = 'C' + CAST(ROW_NUMBER() OVER(ORDER BY ID)+10000 AS NVARCHAR(10))
Note that this works for a select but I did not try for an update.
If the prefix is always "C" I would not want to hold it in the column, so I too would use Scott's approach of "faking" the Prefix "C"
If the "C" can change, over time, then I would have separate columns for the Prefix and the ID and then "fake" the composite column.
What happens when the ID rolls-over to the next order of magnitude? Is
C100001
C1000001
OK, or would it be better to have
C0100001
C1000001
?
With a "faked" column it is much easier to make that change, retrospectively, if it turns out that that is what the users (at some future date!) actually decide they want.