matt me,
You might be on the right track with the hash slice. Consider the following:

#!/usr/bin/perl -w
use strict;

my @keys = qw(one two three four five);
my @vals = ( 1 .. 5 );
my %hash;

@hash{ @keys } = @vals;
print $_, " : ", $hash{$_}, $/ for keys %hash;
[download]

The problem is doing the right thing if the arrays are not the same size, contain duplicates, or if they contain refs. Consider the following:

my $smaller = @array1 > @array2 ? @array2 : @array1;
for my $index ( 0 .. $smaller ) {
    my ($key, $val) = ($array1[$index] , $array2[$index]);
    if ( ! ref $key ) {
        if ( exists $hash{$key} ) {
            if ( ref $hash{$key} ) {
                push @{ $hash{$key} } , $val;
            }
            else {
                $hash{$key} = [ $hash{$key} , $val ];
            }
        }
        else {
            $hash{ $array1[$index] } = $array2[$index];
        }
    }
}
[download]

Of course, "the right thing" is subjective.

Cheers - L~R
Updated: Added duplicates pointed out by davido