One shouldn’t remove them. They are important for search engines like Google.
One can remove them like this:
remove_action('wp_head', 'wp_shortlink_wp_head');
remove_action('wp_head', 'adjacent_posts_rel_link_wp_head');
Here are some additional explanations why they should not be removed and how this effects search engines:
- Core Code insertion
- The related trac ticket
- Google Webmaster Central Article about changes & impact on SEO
In case one removes them, one should really add its own (in case one has changed their links and they are not pointing to the correct urls, that the pagination points to).