<xsl:stylesheet version="2.0"
		xmlns:xsl="http://www.w3.org/1999/XSL/Transform">

<xsl:key name="cb" match="*[not(self::p|self::t)]/change-begin"
	 use="generate-id(following::*[self::p|self::t][1])"/>

<xsl:key name="ce" match="*[not(self::p|self::t)]/change-end"
	 use="generate-id(preceding::*[self::p|self::t][1])"/>

<xsl:template match="*">
 <xsl:copy>
  <xsl:copy-of select="@*"/>
  <xsl:apply-templates/>
 </xsl:copy>
</xsl:template>

<xsl:template match="
		     p/change-begin|p/change-end|
		     t/change-begin|t/change-end
		     " priority="2">
 <xsl:copy-of select="."/>
</xsl:template>

<xsl:template match="p|t">
 <xsl:copy>
  <xsl:copy-of select="@*"/>
  <xsl:copy-of select="key('cb',generate-id())"/>
  <xsl:apply-templates/>
  <xsl:copy-of select="key('ce',generate-id())"/>
 </xsl:copy>
</xsl:template>

$ saxon9 cb.xml cb.xsl
<?xml version="1.0" encoding="UTF-8"?><root>

        <a>
                <p><change-begin/>Foo<change-end/></p>
        </a>

        <b>
                <d>
                        <t><change-begin/>Bar</t>
                </d>
                <d>
                        <t>Foo<change-end/></t>
                </d>
        </b>

        <p>Nothing <change-begin/>to worry<change-end/> about</p>
</root>

________________________________________________________________________
The Numerical Algorithms Group Ltd is a company registered in England
and Wales with company number 1249803. The registered office is:
Wilkinson House, Jordan Hill Road, Oxford OX2 8DR, United Kingdom.