With the exception that in my case the Personal Access Token (PAT) configured for the project was still valid, but the one set on Ogranisation level was expired.
To change the PAT on the organisation level go to: Administration > Oragnization settings > Azure DevOps connectivity management
The error message (404 on the PR) is very confusing and it did not help debugging the situation. We lost a couple of days to this misleading error message. Please fix it.