The documentation isn't clear on whether it expects text or bytes (i.e. encoded text) for each header and for messages. The following basic code gives the warning, indicating it wants the text to be encoded for at least some of them:

#!/usr/bin/perl -w

use strict;
use warnings;

use MIME::Lite qw( );

my $addr = '...@....com';

sub message {
    my ($to_name, $to_addr, $fr_name, $fr_addr, $subject, $body) = @_;
    my $msg = MIME::Lite->new(
        From    => qq{"$fr_name" <$fr_addr>},
        To      => qq{"$to_name" <$to_addr>},
        Subject => $subject,
        Type    => 'multipart/related',
    );
    $msg->attach(
        Type     => 'text/plain; charset=UTF-8',
        Data     => $body,
        Encoding => 'quoted-printable',
    );
    $msg->send;
}

message(  # Control
    'a', $addr,
    'a', $addr,
    'a',
    'a',
);

message(  # Test
    "\x{2660}", $addr,
    "\x{2660}", $addr,
    "\x{2660}",
    "\x{2660}",
);
[download]

The documentation says it handle MIME encoding already, so all we should have to do is the character encoding.

sub message {
    my ($to_name, $to_addr, $fr_name, $fr_addr, $subject, $body) = @_;

    my $fr = qq{"$fr_name" <$fr_addr>};
    my $to = qq{"$to_name" <$to_addr>};

    utf8::encode( $_ ) for $to, $fr, $subject, $body;

    my $msg = MIME::Lite->new(
        From    => $fr,
        To      => $to,
        Subject => $subject,
        Type    => 'multipart/related',
    );
    $msg->attach(
        Type     => 'text/plain; charset=UTF-8',
        Data     => $body,
        Encoding => 'quoted-printable',
    );
    $msg->send;
}
[download]

The warning is gone, and the message displays fine, but looking at the raw email shows that the From, To and Subject fields aren't MIME-encoded. I guess we'll have to do that too.

sub message {
    my ($to_name, $to_addr, $fr_name, $fr_addr, $subject, $body) = @_;

    $_ = encode('MIME-Header', $_)
        for $to_name, $fr_name, $subject;

    utf8::encode( $body );

    my $msg = MIME::Lite->new(
        From    => qq{"$fr_name" <$fr_addr>},
        To      => qq{"$to_name" <$to_addr>},
        Subject => $subject,
        Type    => 'multipart/related',
    );
    $msg->attach(
        Type     => 'text/plain; charset=UTF-8',
        Data     => $body,
        Encoding => 'quoted-printable',
    );
    $msg->send;
}
[download]

And bingo!