I did grant access permission to all pipelines.
Anyway, I found out the problem.
I go to https://sonarcloud.io/organizations/{my_company}/edit and see that my Personal Access Token (under the section Azure DevOps connectivity management) is outdated.
Update it with a new one and now the PR-automated pipelines start working again.
This is somewhat strange from my point of view because CI-triggered pipelines (triggered from new commits to branches like ‘main’ or ‘master’) are still working fine, only PR-automated pipelines fail.