Adding nofollow to a PHP generated Nav

A simple str_replace would do the trick:

$links = paginate_links( $arguments );
$links = str_replace( 'href="', 'rel="nofollow" href="', $links );

echo $links;