Hello!
It is good that the Service principal has Azure Connected Machine Onboarding permission, but then the problem is in other Service principal settings. Check whether the Service principal has access to the subscription and the required Resource groups. Also, check if the Service principal has expired.
More details in this article.
If the above response was helpful, please feel free to "Accept as Answer" and click "Yes" so it can be beneficial to the community.