Is it possible to set a option, and then redirect to another page directly from a admin notice link?

You could use /wp-admin/admin-post.php.

Link:

$url = admin_url( 'admin-post.php?action=somethingunique' );
print "<a href="https://wordpress.stackexchange.com/questions/85825/$url">Update and redirect</a>";

Then you should register a callback for that action:

add_action( 'admin_post_somethingunique', 'wpse_85825_callback' );

And in that callback you can do what you want:

function wpse_85825_callback()
{
    if ( current_user_can( 'manage_options' ) )
        update_option( 'my_option', 'some_value' );

    wp_redirect( admin_url( 'users.php' ) );
    exit;
}

Note this is just some untested code, take it as a direction, not as final solution. 🙂