Vantablack?
In seriousness, there are a several different approaches to brightness mitigation. One is see if the constellation can fly lower, where it would be visible for a shorter time after sunset and before sunrise. The lowest Starlink orbit is about 340km (210mi), which will typically be brightly visible (magnitude +4 to +6) about an hour after sunset and an hour before sunrise. Higher orbits are actually worse; the satellites are dimmer but can stay visible much of the night, and there will appear to be many more of them in the sky, and they will appear to move slower, causing brighter streaks on astronomical exposures.
Another is to see if Starlink's goal can be achieved with fewer satellites. (12000 - 42000 is a LOT of satellites, especially if other companies/nations start making copycat constellations.)
Another, of course, is to apply dark coatings. The downside is that this significantly heats up the satellite, increasing radiation in the infrared (among other side effects), which may greatly interfere with IR astronomy even if the satellite is dark at optical wavelengths.
Another is to design the spacecraft to reflect light upward/outward rather than downward. A Mylar "cone of shame" (pointy end up) with the spacecraft recessed within the cone would geometrically accomplish this, while also shielding the spacecraft from sunlight. The catch is that the solar panels still need sunlight, and the panels are likely the source of most of the apparent brightness, not the body of the spacecraft.
So another is to tilt the solar panels to reflect sunlight upward, during the problematic twilight period. This would reduce power to the satellite while incurring its own power demands, as well as cause wear and tear on the moving parts. But it could be done only on demand when passing specific astronomical sites, e.g. Mauna Kea.
It will be interesting to see what solutions SpaceX comes up with. I do hope Elon and Co. take it seriously.