(.*?)        ""
(nr\.)*      ""
\b\D*        "aaa. bbb ccc nr. ddd"
(\d+)        "23"
[\d\w-]+\b$  "-56"
[download]

It doesn't even need to backtrack, since it found a solution on the first try!

I'd divide the work into two steps:

my ($street, $number) = $address =~ /^(.*?)(\d+)[\d\w-]+\b$/;
$street =~ s/(?:nr\.)*$//g;
[download]

The second regex is not quite sufficient, but I don't have time to perfect it right now.