A slight modification to the Select()
part of your attempt should do :
var xdoc = XDocument.Parse(xml);
var test = xdoc.Root
.Elements()
.Where(e => e.Attribute("id").Value.StartsWith("###"))
.Select(e => e.Attribute("id")).ToList();
foreach (var t in test)
{
//replace id attribute value with string from dictionary
t.Value = myDictionary[t.Value];
}