My XSLT-fu isn't up to it, but yes, you can do it with XSLT.
You're actually only trying to do one clever thing and that's to convert the country code tags into tags.
Its straightforward to iterate over a list of children of a particular node, you can get the tag name of the current node and you can output more or less whatever you want... where I'm uncertain (it not being anything I've ever had to do) is the exact incantation for plucking the node name.
Edit: Too good a question to let go (learning opportunity)
The missing bit of the answer is, of course, on stackoverflow
So that gives you this (based on what I know... I'm sure the copy of regions can be simplified, but I don't know how!):
<?xml version="1.0" encoding="utf-8"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:msxsl="urn:schemas-microsoft-com:xslt" exclude-result-prefixes="msxsl"
>
<xsl:output method="xml" indent="yes"/>
<xsl:template match="/">
<xsl:apply-templates select="countries" />
<xsl:copy>
<xsl:apply-templates select="@* | node()"/>
</xsl:copy>
</xsl:template>
<xsl:template match="countries">
<countries>
<xsl:for-each select="child::*">
<country code="{local-name()}">
<xsl:apply-templates select="region" />
</country>
</xsl:for-each>
</countries>
</xsl:template>
<xsl:template match="region">
<region>
<xsl:value-of select="."/>
</region>
</xsl:template>
</xsl:stylesheet>
Suggestions for improvements welcomed - will amend as appropriate!