I wouldn't split anything or make things more complicated than necessary. keep a %seen hash and start it over at the top of each page or STORE. If there are other "only want to see it once per store" things (like maybe column headers), just add a line similar to the DEPT line code.

my %seen;
while (<DATA>)
{
   %seen = () if (/^\s*STORE/); #start over for each STORE
                               #just /\f/ might be fine too
   next if  $seen{$_};
   $seen{$_}++ if /^DEPT/;  #no more DEPT lines
   print;
}
[download]