Since updating to Mavericks, I can no longer change the color of the Birthdays calendar. If I secondary-click it from the sidebar and select Get Info, it says:
"This calendar automatically displays birthdays listed in your contacts."
Note that when I Get Info on US Holidays, which like Birthdays is in the Subscriptions section (not the On My Mac) section, I can change its color. This Get Info functionality is constant for all On My Mac calendars.