First, there is probably a way to get XML::Simple to output what you want, but anyway, here is the easiest way I found with XML::Twig: the first new creates the root element, then the map creates its children, each created by the second new.

#!/usr/bin/perl -w
use strict;
use XML::Twig;

my %hash= ( name   => 'bob',
            value1 => 'blah',
            value2 => 'blah2',
          );

XML::Twig::Elt->new( newPhone => map { XML::Twig::Elt->new( $_ => $has
+h{$_}) } sort keys %hash)
              ->print( 'indented' );
[download]