The only problem is that I can't 'use' them afterwards. I tried:

foreach (@Dependencies){
    use $_; 
}
[download]

use needs a bareword. Just do the same you did when testing for the modules:

foreach (@Dependencies){
    eval "use $_;1" or die "Can't load '$_'!\n"; 
}
[download]

If you want to avoid string eval for some sort of paranoia (but be aware that require uses string eval under the hood), you can emulate use with require and a call to import():

foreach my $mod (@Dependencies){
    (my $file = $mod) =~ s{::}{/}g;
    $file .= '.pm';
    require $file or die "Can't load '$mod' (file '$file')!\n";
    $mod->import; 
}
[download]