Wordpress - Replacing Icons in the Dashboard

Yes, you can replace existing icons by overwriting them via CSS.

Make sure to check if the existing icon is set via img or background-image and add some CSS to overwrite it with one of the available icons. You can find all available icons and the appropriate selector at the Dashicons Website.

To replace the icon of the Yoast SEO Plugin you can add this snippet to your functions.php:

<?php
add_action( 'admin_head', 'replace_yoast_admin_menu_icon' );
function replace_yoast_admin_menu_icon() {
?>

<style type="text/css">
#adminmenu #toplevel_page_wpseo_dashboard div.wp-menu-image img {
  display: none;
}
#adminmenu #toplevel_page_wpseo_dashboard div.wp-menu-image:before {
  content: '\f108';
}
</style>

<?php } ?>

Further Reading: There is also a nice in depth tutorial from Shea Bunge about Replacing WordPress Admin Menu Icons.

UPDATE: There will be a white icon in the future :)

UPDATE 2: Implemented with v1.6.1

Dashicons to the rescue! Dashicons are the icon font that ships with WordPress 3.8+ by default and powers all the core menu icons.

Start by registering a custom stylesheet for your theme's admin-specific styles in functions.php.

// Admin styles
function wpse134414_admin_styles() { 
    wp_enqueue_style( 'wpse134414_admin_styles_custom_admin_styles', get_template_directory_uri() . '/css/wpse134414_admin_styles.css' , false, '1.0' );
}
add_action( 'admin_enqueue_scripts', 'wpse134414_admin_styles_admin_styles' );

(I actually prefer to do this in a custom mu-plugin which requires a slightly different snippet, but I'll go with a theme admin styles for this answer.)

Then make that stylesheet—this example has it in the /css/ folder of the active theme—and use a rule like this to target the icon with the right content value to get the icon of your choosing (find these on that dashicons link above):

/* Better Yoast SEO Admin Icon */
/* hide the default icon */
#toplevel_page_wpseo_dashboard .wp-menu-image img {
    display: none;
}
/* add the new dashicon */
#adminmenu #toplevel_page_wpseo_dashboard div.wp-menu-image:before {
    content: "\f107";

/* style the icon with CSS to make it re-yoasty */
    color: #ef8e02;
    opacity: 0.7;
}
#adminmenu #toplevel_page_wpseo_dashboard a:hover div.wp-menu-image:before {
    opacity: 1;
}

That icon is the wrench icon from Dashicons that actually looks kind of like the negative space in the default icon.

While the color and hover state are probably overkill and actually counter to the reason you want to replace the icon in the first place, I include them just to point out that you can use CSS to styles these icons however you want.