I tried all kinds of things and what worked was the following.
Export your current settings
Go to Wordfence>Tools and select the Import/Export Options tab and click the Export Wordfence Options. Wordfence will generate a token that you can copy and save to import later.
Delete Wordfence data on deactivation
Enable the option Delete Wordfence tables and data on deactivation under Wordfence>All Options>General Wordfence Options. If you then deactivate the plugin, all the Wordfence tables will be deleted. You can then choose to activate Wordfence again to get a fresh installation.