What is the best way to implement the ability to allow multiple colors on a duplicated mesh?

I have multiple beads that all share the same mesh. However, the beads also need to be different colors:

I achieved the above using random colors on the material, however that resulted in multiple draw calls.
Is there a preferred way to achieve the same effect, but reducing the draws drastically?

Yes, use vertex colours. Assign colours to the mesh.colors array of each object, and adjust the shader of the shared material to use those mesh colours - then you can draw all those beads in a single draw call.