How can I minimize Black Market set up and clean up time?
Here's an option used by Donald X. Vaccarino. Instead of using the normal randomizer cards, take one card from each kingdom stack and use those for randomizer cards. When you're doing normal randomization, just add the chosen cards to their respective kingdom stacks, and after the game, take one card from each stack to add back to the new randomizers.

Then, when you play Black Market games, you will have a ready-made Black Market deck! The 10 cards in the kingdom will already be out of the randomizer deck, and the backs are the normal backs so you don't have to pull cards from the box like you do with your option 3.

Donald X. Vaccarino talks about this method here.