The solution already posted might be improved by making a few small changes:

use strict;
use warnings;

my $str=<<'_END_DATA_';
lease 10.2.56.40 {
        starts 3 2003/08/20 10:37:28;
        ends 3 2003/08/20 22:37:28;
        hardware ethernet 00:20:af:52:12:0f;
        uid 01:20:af:52:12:0f;
        client-hostname "Telephone";
}
lease 10.2.56.75 {
        starts 3 2003/08/20 09:57:11;
        ends 3 2003/08/20 21:57:11;
        hardware ethernet 00:ef:18:ae:52:83;
        uid 01:00:ef:18:ae:52:83;
        client-hostname "beast";
}
lease 10.2.56.77 {
        starts 2 2003/08/19 21:13:05;
        ends 3 2003/08/20 21:13:05;
        hardware ethernet 00:02:95:9b:78:18;
        uid 01:02:0b:95:9b:78:18;
}

_END_DATA_

my $l = '10.2.56.77';
if ($str =~ /^(lease\s\Q$l\E[^\}]+?^\})/m) {
  print "$1\n";
}
[download]

First, I would make the end delimiter for the heredoc a bit more distinct, but that's a side issue.

I would rewrite the main portion as:

my $l = '10.2.56.77';
if ($str =~ /^(lease\s\Q$l\E[^\}]+?^\})/m) {
  print "$1\n";
}
[download]

The .* from the original can get you into trouble, you're better off explicitly stating what kind of character you don't want to see (the "}" in this case.)

The $& variable also slows down the program considerably. See the perlre section of the perl docs.