The root cause of the issue was found, the user who created the PAT (a service account made for the task) was set to the Stakeholder access type where it should have had Basic instead. Changing the user type gave access to the repositories.
Should someone else face the same issue in the future, they can try the following:
Curl azure devops API with their AzureDevOps organization name to get the list of projects, and then for each projects, fetch the list of the repositories. If nothing is returned while fetching the repository list, it means there is something wrong on AzureDevops configuration and this is why SonarCloud can’t access the repositories.
Fetch projects: https://dev.azure.com/{AzureDevopsOrg}/_apis/projects?api-version=6.0
Fetch repositories: https://dev.azure.com/{AzureDevopsOrg}/{projectId}/_apis/git/repositories?api-version=6.0
The following command can be used
curl --location --request GET '<URL>' \
--header 'Authorization: BASIC <B64_PAT>'
And the documentation to generate the B64_PAT is here, section “use a PAT”. The PAT generated for SonarCloud should be used.