そもそもphoto_idから画像のurlを取得するAPIが用意されていれば話が早かったのですが、そんなAPIが無いようなので、getInfoで取得できる情報からurlを生成しようと思います。

#"/usr/bin/env perl

use strict;
use warnings;

my $photo_id = 123456;

my $fa = Flickr::API->new({
    key => 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx',
    secret => 'xxxxxxxxxxxxxxxxxxxx',
    unicode => 0,
});

my $res = $fa->execute_method(
    'flickr.photos.getInfo',
    {
        photo_id => $photo_id,
    }
);
die unless ( $res->{'success'} );

my $url = '';
for my $tree ( @{ $res->{'tree'}->{'children'} } ) {
    next unless ( exists $tree->{'name'} );
    next unless ( $tree->{'name'} eq 'photo' );
    $url = sprintf(
        'http://farm%d.staticflickr.com/%d/%d_%s.%s',
        $tree->{'attributes'}->{'farm'},
        $tree->{'attributes'}->{'server'},
        $tree->{'attributes'}->{'id'},
        $tree->{'attributes'}->{'secret'},
        $tree->{'attributes'}->{'originalformat'}
    );
    last;
}

print $url;

結構ざっくりですが、こんな感じでurlが生成可能です。
サイズ違い(_sとか_mとか)は適時追加すれば宜しいかと。