Fazer uso de um cte recursivo me permite obter o resultado que você está procurando. Como mostra a seguir. Mas pelo menos não é um cursor / while-loop;)
declare @tmpConstraint table (ID int , Constraint_Value varchar(256))
insert into @tmpConstraint values
(1, '(OldVal_1) (OldVal_2)'),
(2, '(OldVal_2) (OldVal_1)')
declare @myXML XML
set @myXML = N'<qaUpdates>
<qaUpdate><old>OldVal_1</old><new>NewVal_1</new></qaUpdate>
<qaUpdate><old>OldVal_2</old><new>NewVal_2</new></qaUpdate>
</qaUpdates>'
declare @xmlData table (oldValue varchar(256), newValue varchar(256))
insert into @xmlData
select
oldValue = Child.value('(old)[1]', 'varchar(50)'),
newValue = Child.value('(new)[1]', 'varchar(50)')
from @myXML.nodes('/qaUpdates/qaUpdate') as N(Child)
O acima foi apenas configurado para o seguinte.
;with cte (ID, Constraint_Value, CLevel)
as
(
select c.ID, c.Constraint_Value, 1
from @tmpConstraint c
union all
select p.ID, cast(replace(p.Constraint_Value, x.oldValue, x.newValue) as varchar(256)), p.CLevel + 1
from cte p
join @xmlData x on p.Constraint_Value like '%' + x.oldValue + '%'
)
update c
set c.Constraint_Value = t.Constraint_Value
from @tmpConstraint c
join (
select
*,
rn = row_number() over (partition by ID order by CLevel desc)
from cte
) t on t.ID = c.ID and rn = 1
select * from @tmpConstraint
