The trick about using seek and read is that in order to seek to a position from the end of a file, you have to specify a negative number for the offset amount. For example, if the log files for successful runs always have the phrase "Normal termination\n" as the very last thing in each file, that's just 19 bytes you need to read from the end -- but let's pad that a bit, just to be safe:

#!/usr/bin/perl

use strict;

my $prefix="Kick";
my $Restart="Restart.data";

open( RESTART, $Restart ) or die "Unable to read $Restart: $!\n";
my $AlreadyDone = <RESTART>;
my ( $jobs_run ) = ( $AlreadyDone =~ /(\d+)/ );

for ( my $j=0; $j<=$jobs_run; $j++)
{
    my $job_title = sprintf( "%s%04d", $prefix, $j );
    if ( open( my $fh, "<", "$job_title.log" )) {
        seek( $fh, -24, 2 );
        read( $fh, my $job_end, 24 );
        unlink "$job_title.data" unless ($job_end =~ /Normal/);
    }
    else {
        warn "Unable to read $job_title.log: $!\n";
    }
}
[download]

Some miscellaneous notes:

• I didn't see any clear rationale for using the "-s" option on the shebang line. If you have a reason for that in your "production" script, it's fine, but it seemed unnecessary here.
• Your method of getting a numeric value from the "Restart.data" file was strange. I think a regex match for the numeric is better/safer.
• When you decide to report an error message regarding a failed open() call, including "$!" in the message can be very helpful.
• Overall, I think the overhead of opening and closing data files in perl will be less (given that you are only reading the last couple dozen bytes from each file), than the OS overhead of creating and tearing down 100's of subshells for running "tail", just as the use of perl's unlink function is fairly certain to be more efficient than a series of subshells that invoke the unix "rm" command.
• Notice how easy it was to add use strict

(updated to add a missing close-paren -- forgot to do "perl -cw" before hitting "create")