Did you change the line so that it looks for two digits instead of any arbitrary number of digits, and now you're padding single digit numbers with a zero? (That's what it sounds like)
If so:
$string =~ s/\^(\d{2})/sprintf("%".int($1)."s")/ge;
Of course, you can use \d{1,2} instead of \d{2} if you want to match either 1 or 2 digits, instead of only exactly two.