How to change the link “Edit my profile”?

The filter hook edit_profile_url does that. It returns the URL and provides the User ID so you can use it for some customization of the new URL.

add_filter( 'edit_profile_url', 'modify_profile_url_wpse_94075', 10, 3 );

/**
 * http://core.trac.wordpress.org/browser/tags/3.5.1/wp-includes/link-template.php#L2284
 *
 * @param string $scheme The scheme to use. 
 * Default is 'admin'. 'http' or 'https' can be passed to force those schemes.
*/
function modify_profile_url_wpse_94075( $url, $user_id, $scheme )
{
    // Makes the link to http://example.com/custom-profile
    $url = site_url( '/custom-profile' );
    return $url;
}

Q&A of interest: Where to put my code: plugin or functions.php?