I would definitely advise you to use a template module (I use Text::Template myself): it will work out-of-the-box, won't have bugs and give you way more features than what you would code yourself. Plus you would not have to craft the kind of regexp you will see below.

Of course that said, I can't resist the temptation to give you a proper regexp (all solutions so far will fail for <~hash{foo~bar}~>):

I am totally unable to explain the regexp clearly, so try it, look at the regexp doc and above all, do yourself a favor and buy a copy of Mastering Regular Expressions in which Jeff Friedl does a great job at explaining this sort of things.

update: OK let's try to explain it anyway:

s/<~( 
           (
            [^~]*      # match anything but a ~
            (~(?!>))?  # match a ~ NOT followed by a >
                       # the non > char is not captured so
                       # it is still available for matching 
            )*         # match this sequence again
           )/expand($1)/x;
[download]

The regexp captures all characters up to a ~
if the ~ is followed by a > it stops there
if the tilda is NOT followed by a > then the optional block is matched, the following (non >) character has not been used so the outer ()* starts with this character and starts matching again until a ~

Re-update: the expanded regexp was missing a closing paren, I fixed it