I was able to solve the issue by generating backup codes. If they were generated before already, try regenerating them.
The prompt above happened only when accessing the web login for connecting the Nextcloud app so I tried many things including logging in and out, creating a new account, trying the .deb version, re-sharing folders, changing passwords, etc., but when the prompt was also present in the newly-created account, before accepting that app passwords are the way to go, I decided to try generating backup codes.
For reference, my version is 31.0.4.
I hope the trick helps with your instance, too.
EDIT: On another account, setting up TOTP solved the issue.