How to add nofollow to the_post_navigation?

The only option I see is using {$adjacent}_post_link hook and replacing the fragment of final link or prepare the link yourself from scratch.

Replace:

add_filter( 'next_post_link', 'se334246_nofollow_link', 20, 5);
add_filter( 'previous_post_link', 'se334246_nofollow_link', 20, 5);

function se334246_nofollow_link( $output, $format, $link, $post, $adjacent )
{
    $search = sprintf('rel="%s"', $adjacent);
    $output = str_replace($search, 'rel="nofollow"', $output);
    return $output;
}

From scratch:

add_filter( 'next_post_link', 'se334246_nofollow_link', 20, 5);
add_filter( 'previous_post_link', 'se334246_nofollow_link', 20, 5);

function se334246_nofollow_link( $output, $format, $link, $post, $adjacent )
{
    if ( !$post )
        return $output;

    $title = $post->post_title;
    $title = apply_filters( 'the_title', $title, $post->ID );
    $permalink = get_permalink( $post );

    $inlink = str_replace( '%title', $title, $link );
    $inlink = str_replace( '%date', '', $inlink );

    $inlink = '<a href="' . $permalink . '" rel="nofollow">' . $inlink . '</a>';
    $output = str_replace( '%link', $inlink, $format );

    return $output;
}