It would be quite easy. You are overcomplicating it. Presumably there is a placeholder token in all lines of dialog where the WoL's personal pronouns appear. Presumably the game replaces the placeholder in all dialog occurrences with the corresponding pronoun via a conditional that calls the function that returns the character's sex. These are reasonable presumptions that any competent programmer would make.
I don't care how bad the game's code base is; there's no way it would take more than twenty minutes to add a gender selector to character creation, add the gender field to the character data, and modify the function that returns the character's sex during dialog pronoun replacement to return the character's gender instead. Then another twenty minutes to add a quick validation into the character loader that silently fixes any existing character data that doesn't have a gender selected to default to the gender matching the character's sex. Hardly any time at all for each localization team to provide add the word for "gender" into the localization dictionary. Maybe a little bit more time to code a dialog box that gives all existing characters the opportunity to set their gender on the first load after the feature is added.
As far as technical difficulty is concerned, this is not a difficult ask, by any means.