oh forgot to add
<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />
Thanks for your request. I think, in your case you should use ReplaceEvaluator:
In ReplaceEvaluator you can use Documentbuilder, so you can specify formatting of the replacement.
Regarding \n characters, you can try replacing \n character in the replacement string with com.aspose.words.ControlChar.LINE_BREAK.