A few suggestions:

1. Don't pre-declare your variables. Only declare them as you need them. In general, the only reason to declare a variable outside the logic structure within which it is set is if you're going to use it outside that logic structure. As you never use any of these variables outside the loop, declare them inside. :-) (That will also remove the need to Clear that annoying array.)
2. Don't do if ($choice =~ /l/i). Instead, do

   $choice = lc $choice;
   
   # ... later ...
   
   if ($choice eq 'l')
   [download]

   It makes your intent clearer. (That it's also more efficient is a bonus.)
3. The code for your user-picked list is interesting. I would have written it as:

   my $filename = 'birthday.db';
   
   # ... later ...
   
   open IN, $filename || die "Cannot read '$filename': $!\n";
   print <IN>;
   close IN;
   [download]

   Then, I realized that there is a perfectly valid reason to do it your way - if the file is really large. You chose the memory-light method. I chose the coding-light method. *shrugs* TMTOWDI.
4. The last point illustrated something - anytime you have a constant, you should look at defining it up above. That way, you only define it once, making it easier to change. Also, your code is easier to read. So, I would rewrite another portion as such:

   use constant CHOICE_LIST => 'l';
   my $db_file = 'birthday.db';
   
   # ... later ...
   
   if ($choice eq CHOICE_LIST)
   {
       open(IN, $db_file) || die "Cannot read '$db_file': $!\n";
       print <IN>;
       close IN;
   }
   [download]

5. In your add-an-entry code, I would add some validation checks. Just to make sure that stuff in your database looks good.
6. Your modify/delete code is very ... convoluted. I'd do the following:

   if ($choice eq CHOICE_MODIFY)
   {
       # Use a hash, not an array. The assumption here is that the names 
   +will be unique.
       open(IN, $db_file) || die "Cannot read '$db_file': $!\n";
       my %birthdays = map { chomp; split ':' } <IN>;
       close IN;
   
       # Print out a list of the names and birthdays
       print "$_ => $birthdays{$_}\n" for sort keys %birthdays;
   
       print "Enter record to modify: "; chomp ($key = <STDIN>);
       print "(M)odify or (D)elete? "; chomp ($choice = <STDIN>);
   
       $choice = lc $choice;
       if ($choice eq 'm')
       {
           print "Enter person's birthday: "; chomp ($date = <STDIN>);
           $birthdays{$key} = $date;
       }
       elsif ($choice eq 'd')
       {
           delete $birthdays{$key};
       }
   
       open OUT, $db_file || die "Cannot overwrite '$db_file': $!\n";
       print OUT "$_:$birthdays{$_}\n" for keys %birthdays;
       close OUT;
   }
   [download]

   This way, you re-use as many lines of code as possible.
7. I am impressed with your avoidance of a lot of common newbie pitfalls, such as not checking the results of open and the like.

------
We are the carpenters and bricklayers of the Information Age.

The idea is a little like C++ templates, except not quite so brain-meltingly complicated. -- TheDamian, Exegesis 6

Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.