modify('replace value of (/attrs/attr[. = sql:variable("@OldValue")]/text())[1]
with sql:variable("@NewValue")')
Your second attempt is actually just missing to specify that it is the text() that should be replaced. This will also work.
modify('replace value of (/attrs/attr[text() = sql:variable("@OldValue")]/text())[1]
with sql:variable("@NewValue")')