I kind of described it already, but here's one brainstorm that is untested:

use strict;
use warnings;

my $string = <<HERE;
A long time ago
in a galaxy far far away
a great adventure took place.
HERE

sub textbox {
    my( @lines ) = split /\n/, $_[0];
    chomp @lines;
    my $longest = 0;
    foreach my $line ( @lines ) {
        my $size = length $line;
        $longest = $size if $size > $longest;
    }
    foreach my $line ( @lines ) {
        my $prepad = ' ' x ( ( $longest - length( $line ) ) / 2 );
        $line = $prepad . $line;
        $line .= ' ' x ( $longest - length( $line ) );
        $line = '* ' . $line . ' *';
    }
    my $outline = '*' x ( $longest + 4 );
    push @lines, $outline;
    unshift @lines, $outline;
    return join( "\n", @lines ) . "\n";
}

print textbox( $string );
[download]

This could use some streamlining, but I left it reasonably verbose so that it would be clear what's going on. Enjoy!