Sure. Here's how for the Note 4:
1. Select the Calendar app
2. Select the menu bar at the top right of the screen
3. From the drop down menu, select Calendars
4. Select the Palette at the top right of the screen (your calendars will already be listed and checked)
5. Select a specific calendar or feature to change that color
I know this is an old thread but this answer does not work for EXCHANGE / ActiveSync accounts, as the option to change the color is missing, surprisingly!
Apparently, you simply cannot change the color of Exchange calendars in the Google Calendar app. So you must deal with whatever random color the app chooses to use for your Exchange calendar. In my case, it's an ugly purple color that isn't very easy to read.
With all of that being said, there is a band aid work-around for this, but users shouldn't have to go through this!
1) Download an app called "CalendarColors Trial" from the Google Play Store
(Do not open the app yet after you install it)
2) The trial version only lets you change the color of the VERY FIRST calendar in the list, so you must first HIDE all other calendars (via the Calendar app settings) if your Exchange calendar doesn't show up first (I don't recommend paying the $3 price for an outdated/unsupported app just to change a color).
3) Once you've hidden all other calendars (except your Exchange calendar), THEN you open the app and change the color of the Exchange calendar.
This worked on my new Galaxy S6 Edge surprisingly. But again, users should not have to rely on outdated/unsupported apps just to change a friggin calendar color!
Hope this helps for anyone searching...