Solution:
This should work just fine, but I can see that you have already tried it:
remove_action('wp_head', 'wp_shortlink_wp_head', 10, 0);
Are you putting this in your functions.php file? Please make sure you did not put it in the middle of a function.