I disagree with the two options put forward.
In the context of shared address books, one must also consider that sometimes one person has a ‘private’ e-mail address or some such from a contact that is not supposed to be shared. Also, in the note field people may add info that concerns their personal interactions with the contact, again not to be shared. Furthermore, groups are not always supposed to be shared.
The point I wish to make is that it is hard to make the distinction between what is supposed to be shared or not and that this line is not drawn at the vCard spec border. I do agree that the ‘starred’ feature should ideally be dealt with as a group (category), but devices/clients usually don’t support this well, as you indicated.
A possible solution is the following: Android merges data about the same contact from different sources. So create two addressbooks, one with shareable date, one with non-shareable data; sync them both, only share the former. This approach can also be used with the ‘multiple devices’ issue. The hard/non-nice part here is to get the right address book to pick up the ‘starring’ on the device: because (my) contact viewing/editing app(s) doesn’t expose that in the editor, but in the viewing part, where I cannot choose which backend to edit. I got it to do that by disabling syncing for one, then starring, then enabling syncing again.
I am actually doing something like this right now: DAVdroid does not support ‘RELATED’ yet, but CardDav-Sync does (in the nonstandard way Google contacts exports version 3.0 vCards); so I sync the same address book using the two different clients to access this data. It works (although I do get duplicates for some fields, such as URLs and ADRs that probably get injected differently into the Android contacts store by the two apps). (I would of course prefer to use a single vCard 4.0-based app… but anyway.)