how to replace user's names with random names?
If you decide that the Update is too slow, I suggest the following will be about 1000 times as fast.

Loop (can be done in a Stored Proc)...


[Re]Create a table with randomly ordered set first_names, with a `PRIMARY KEY of 1..5000.  Ditto for last_names (a second table).
Multi-table UPDATE the 'next' 5000 rows joined to the two random tables.  Use ON Users.id % 5000 = RandomFirstNames.id (etc)


End Loop

Shuffling the table (step 1 of the loop) is something like

CREATE TABLE RandomFirstNames (
    id SMALLINT UNSIGNED AUTO_INCREMENT,
    first_name VARCHAR(...),
    PRIMARY KEY(id) )
SELECT first_name FROM FirstNames ORDER BY RAND();


After OP's UPDATE

Don't do 

SELECT count(id) INTO count_names FROM _RandomFirstNames;


Instead, do this once:

SELECT @mask_ct := COUNT(*) FROM _masked_names;


and use @mask_ct instead of count_names;

As for the skipped ids, CREATE TABLE _RandomFirstNames without an id, then ALTER TABLE _RandomFirstNames ADD id INT UNSIGNED AUTO_INCREMENT PRIMARY KEY; to get the ids.  This should give you ids without gaps (unless you are on a multi-Master cluster of any kind).