Contact names not showing in Messages on High Sierra
The problem seems to be that the phone numbers in your contacts have lost the proper format. They should be in the form (123) 456-7890 and they have been formatted as 1234567890.  It seems that iOS does a really literal comparison and it can't resolve this difference.

I fixed this on my iPhone 5s running iOS 12 by changing my region from the US to Canada. That evidently forces a re-formatting of the erroneous numbers. Then I changed it back to the US. Note that my contacts were synced with Google/Gmail. I think this should also work for iCloud, but your mileage may vary.

Go to Settings app → General → Language &amp; Region → Region, tap on Canada, then tap Done. (I bet selecting any different region would work). The change takes a bit of a time. When it is complete, look at your recent calls, voicemails and messages - they should be displaying names. Look at your contacts - phone numbers should be correctly formatted. If so, the problem should be fixed. In any case, change the region back to United States.