How can I ensure a referenced entity is cached separately per paragraph?
So the easiest option likely is to just disable caching completely for the embedded entities. 

In hook_entity_view(), unset $build['cache']['keys']. They are then still cached as part of the paragraph render cache, but don't have their own cache entry anymore.

To avoid not caching them when they are shown somewhere else, you should use a special view mode when you integrate them in paragraphs and only disable caching for that.

Note that you could also set max-age = 0 but that means "this content must not be cached at all", that information would bubble up to the paragraph and host entity and none of those would be cached anymore. That's not what you want.

Or you could change your approach and apply that color through a class that is set on the paragraph level, without changing the HTML of the embedded entity. Doesn't work for everything, but for a simple color change, that is likely easier to implement.