How do you get iPhone to share contacts with Mac Messages app?
I have been having this same problem and as I go through this thread I found that I could answer yes to everything, but the problem persisted. 

I ended up opening the Contacts page on my Mac and while the contacts I needed were in "All Contacts" they were not in the "On My Mac" so I highlighted them all under "All Contacts" and did a drag and drop into "On My Mac" it fixed almost all my problems. 

The ones that it didn't fix I found out that the formatting on the phone number themselves were not correct. For example the one on Mac messenger was 1(234)567-8900 while the contact card did not have a 1... so, (234)567-8900. Changing those two things fixed everything.