Something to know...
I think there is some criteria that can be met that will cause it to reset your lockdown records. Make sure both devices are locked when plugging them into each other for the time being just to rule that out.
Somethings to try...
Like mentioned, make sure your hotspot on your phone is set to off. The phone is asking if its ok for the computer to use your internet via USB if its on...
Are you the Admin of the computer? Are both the computer and your phone using the same AppleID? Is there other users on that computer? What is there system access level?
Two factor security turned on with both the Mac and iPhone?
Goto System Preferences > AppleID > Name Phone Email. Make sure your phone number is in there.
Goto System Preferences > AppleID > Password & Security. You should see "Trusted Phone numbers : #" Click the edit button next to that and make sure your phone number is in there and its verified.
Goto Settings > AppleID > Name. And Password Security on the iPhone and verify the information including phone numbers all match up there.
Finally, I haven't verified this but I've read that certain anti-spyware, anti virus, anti malware and/or those "Mac cleaner!" programs can block proper access or negate changes to the systems lockdown records (/var/db/lockdown). Disable them if you have them, if its a Mac Cleaner program just delete it.
Hope something here helps you out.