Using just the Integration profile doesn't allow access to standard objects so it is advised to create a Permission Set (a.k.a PS) to allow CRUD access to standard objects like Accounts, Contacts, or Leads. See here and here.
It is also advised to not select a License
when creating the PS, which I did.
But after configuring the PS and upon assigning it to the user, I get the following error:
Failure : Can't assign ABC permission set to XYZ user. The user license doesn't allow the permission: Read Lead
OR
Failure : Can't assign ABC permission set to XYZ user. The user license doesn't allow the permission: Create Contact
OR
Failure : Can't assign ABC permission set to XYZ user. The user license doesn't allow the permission: Delete Contact
I'm not sure how to fix this issue and it is not pointed out anywhere.