sed, as is almost always the case when it comes to XML, is the wrong thing to use here. Use a tool that understands the format natively, like xmlstarlet. One of its many modes allows you to assign a new value to an attribute or element that matches an XPath expression (Which is a much better and more precise way to match part of an XML document than trying to use regular expressions):
$ xmlstarlet ed -u '/root/list/pair[@name="id"]/@Value' -v othervalue file.xml
<?xml version="1.0"?>
<root>
<list>
<pair name="id" Value="othervalue"/>
</list>
<list>
<pair name="place" Value="US"/>
</list>
</root>
In xmlstarlet ed, -u xpath means "Update the bit that matches the given XPath expression" and -v blah means "With this value".
Add the --inplace option to modify your XML file in-place once you've verified it does the right thing:
xmlstarlet ed --inplace -u '/root/list/pair[@name="id"]/@Value' -v othervalue file.xml