Change Notice of Password change email subject?

The $change_mail variable that you’re filtering has a subject value that you can modify the same way you modified the message:

// Replace the default password change email
add_filter('password_change_email', 'change_password_mail_message', 10, 3);
function change_password_mail_message( $change_mail, $user, $userdata ) {
    // Call Change Email to HTML function
    add_filter( 'wp_mail_content_type', 'set_email_html_content_type' );
    $message = "<p>Test HTML email</p>";

    $change_mail[ 'message' ] = $message;
    $change_mail[ 'subject' ] = 'My new email subject';

    return $change_mail;
}

(I removed your call to remove_filter() because it wouldn’t do anything. Nothing after return will run.)