When you save permalink settings, is there the following notification at the bottom of page?
If your .htaccess file were writable, we could do this automatically,
but it isn’t so these are the mod_rewrite rules you should have in
your .htaccess file. Click in the field and press CTRL + a to select
all.
I’m asking because the behaviour you described may be caused by non-existing or non-writable .htaccess file in your WordPress root.
If you have a shell access to the server environment (or you work locally), you can create this file and add writing permissions:
cd your_wp_directory
touch .htaccess
chmod a+w .htaccess
After that, save permalink settings again.