Sure. See the following link: http://www.hookedonlinq.com/LINQtoXML5MinuteOverview.ashx
XElement xml = new XElement( "Response",
new XAttribute( "TaskId", "2429" ),
new XElement( "message", "Run for cover" ),
new XElement( "element",
new XAttribute( "location", "proj\survival.cs" ),
new XAttribute( "status", "running" ) ),
new XElement( "element",
new XAttribute( "location", "proj\run.cs" ),
new XAttribute( "status", "running" ) ) );
You can see above that it builds out the XML structure with nested calls. All you need to do is include the 'new Attribute' call as part of the LINQ structure to generate a new attribute.
UPDATE: If you want to add attributes to the result of a query, do the following:
var query = from node in xml.Descendants( "element" )
select node;
foreach( var element in query )
{
element.SetAttributeValue( "status", "running" );
}