The difference is scoping. In the latter case, the variables $key and $value persist outside the loop, whereas they go out of scope once the loops finishes its last iteration in the former case. For example, the following would be valid syntax for the second case, but not the first:

my($key, $value);
while(($key, $value) = each(%hash) ) {
    print "$key => $value\n";
}
print "The last pair was $key => $value\n";
[download]

It's discussed in For LoopsDeclarations.