Приведенный выше «лучший ответ» работает, если вам все равно, что новый узел «p» заканчивается в конце родительского. Чтобы заменить его там, где он есть, используйте:
string xml = "<span>sometext</span>";
XmlDocument xDoc = new XmlDocument();
xDoc.LoadXml(xml);
// If you have XmlNode already, you can start from this point
XmlNode node = xDoc.DocumentElement;
XmlElement clone = node.Clone();
XmlNode parent = node.ParentNode;
XmlElement xElement = xDoc.CreateElement("p");
xElement.AppendChild(clone);
parent.ReplaceChild(xElement, node);