Here is something that look a bit cleaner. There are lots of comments. no warnings, /usr/bin/clear won't port. Hardcoded file paths are bad. Not checking the result of file opens is bad. Redundant code is bad ie most of your if/else do 'cls'+exit. You don't really need Term::Readline or Shell. Use File::Copy if you must.

#!/usr/bin/perl

use strict;
use warnings;

my $DATFILE = "c:/store.txt";

my @teams = qw(
    Arsenal     Bolton              Villa       Chelsea     Middlesbro
+ugh 
`   Newcastle   Birmingham          Blackburn   Palace      Fulham 
    Liverpool   ManchesterCity      Norwich     Portsmouth  Spurs 
    WBA         ManchesterUnited    Southampton Charlton    Everton 
);

clearscreen();

# if we don't have a datfile we HAVE to INIT it!!!
init_file(\@teams) unless -e $DATFILE;

# now we can read the datfile becuase it exists, 100% guaranteed
open F, $DATFILE or die "Can't read $DATFILE, Perl says $!\n";
chomp ( my @values = <F> );
close F;

print "
---------------------------
1. Update Teams
2. Check previous Results
3. Backup Storage File
4. Quit
---------------------------

Option: ";

chomp( my $reply = <STDIN> );

clearscreen();

if ($reply == "0") {
    init_file(\@teams);
}
elsif ($reply == "1") {
    team_update(\@values, \@teams);
}
elsif ($reply == "2") {
    team_find(\@values);
}
elsif ($reply == "3") {
    storage_backup();
}
else {
    print "Exiting\n";
}

exit 0;

#-----------------------------------------------------------------
# subs
#-----------------------------------------------------------------

sub clearscreen { $^O =~ m/Win32/ ? system('cls') : system('clear') }

sub init_file {
    my ($teams) = @_;
    open F, ">$DATFILE" or die "Can't write $DATFILE, Perl say $!\n";
    print F "$_\n" for @$teams;
    close F;
}

# yada
[download]