The xcrun notarytool history shows 500 error too. It looks it fails when app specific login is used and not for the other authorization methods.
It works via App Store Connect API:
Create API key and download it https://appstoreconnect.apple.com/access/api
Copy key-id and issuer from same page
Store to keychain
xcrun notarytool store-credentials Notarize --key apple-connect-api-key.p8 --key-id 1234567 --issuer 11f28c89-0bbc-47b8-bb65-ad719eb08e4c
Use to notarize
xcrun notarytool submit ParetoUpdater.zip --team-id 12345678 --progress --wait --keychain-profile "Notarize"