The listed examples didn't indicate to me that we need to worry about anything other than the first number, and adding 2000 to a 1 digit number definitely results in a 4 digit one. :-)

But if that's your spec, then try s/(\d?\d)-(\d?\d)-(\d?\d)/sprintf("20%02d-%02d-%02d", $1, $2, $3)/eg