TIMTOWTDI...

use warnings;
use strict;
use Test::More tests=>12;

my $in = "\N{U+CF} \N{U+2764} \N{U+1F42A}";
is utf8cut($in, 11), "\N{U+CF} \N{U+2764} \N{U+1F42A}";
is utf8cut($in, $_), "\N{U+CF} \N{U+2764} " for 10,9,8,7;
is utf8cut($in,  6), "\N{U+CF} \N{U+2764}";
is utf8cut($in, $_), "\N{U+CF} " for 5,4,3;
is utf8cut($in,  2), "\N{U+CF}";
is utf8cut($in, $_), "" for 1,0;

sub utf8cut {
    my ($str, $bytelen) = @_;
    utf8::encode($str);
    $str = substr $str, 0, $bytelen;
    $str =~ s/(?: [\xC0-\xDF] | [\xE0-\xEF] [\x80-\xBF]?
        | [\xF0-\xF7] [\x80-\xBF]{0,2} )\z//x;
    utf8::decode($str);
    return $str;
}
[download]

Updates 1 & 2: As per replies, fixed by removing the code which did special handling when !utf8::is_utf8($str) (and the corresponding tests), which I had originally added to the code as an ill-conceived afterthought.