How can I undo accidentally duplicated user metadata key values?

This should do what you want:

global $wpdb;
$wpdb->query("
    DELETE FROM $wpdb->usermeta
    WHERE meta_id NOT IN (
        SELECT MIN(meta_id)
        FROM $wpdb->usermeta
        GROUP BY user_id, meta_key, meta_value
    )"
);

Maybe you should first back up your table, though.