Changing the wife is actually easier than changing her name, if you are sure that Patience and Alice are really two different persons. You should have evidence to back up your change and make a Note on the relevant biographies, citing the evidence and explaining the changes you have made and why.
To remove Patience, go to the Edit screen on William's profile and choose Edit family > Spouses > add/remove spouse. Choose Remove, then enter Patience's Wiki ID #.
To add Alice, if she already has a Wiki ID, do the same thing with Add. If she does not, choose Add and create a new profile for her, with an appropriate source.