Is it possible to create a Category Item Object and Associate it with a Contact using the EWS Managed API?
You can assign a Category to any Object in a Mailbox using the Categories property https://msdn.microsoft.com/en-us/library/microsoft.exchange.webservices.data.item.categories(v=exchg.80).aspx .
For a particular color/description to be show in Outlook or OWA the category you pass in must match an Item in the Master category list. You can read/modify the Master category list in a Mailbox using EWS eg https://social.msdn.microsoft.com/Forums/en-US/e5c5f072-0b5c-49ce-9db7-57f76f5e011e/edit-master-category-list-in-exchange-2010-via-ews?forum=exchangesvrdevelopment and https://social.msdn.microsoft.com/Forums/en-US/a3917500-2bbc-4def-98b4-696e49efed6f/adding-categories-to-a-users-master-category-list-in-exchange-2010-using-ews?forum=exchangesvrdevelopment