Plan + Market Square
On weak BM boards this can be a strategy in and of itself. Just open Plan / MS and trash Estates and Coppers, gaining roughly one Gold at a time this way. Sometimes you'll get two! You should then be ready to green. Obviously this isn't that strong but it can work out OK if you're otherwise bored.
That puts the "potentially" into "potentially useful" for sure.
Well, there is a grain of usefulness there: Market Square basically "combos" with any self-trasher (as opposed to what beginners might assume was primarily a "reaction" to a trashing attack.) The only trouble with using Market Square with most trashers is getting them to match up in the same hand, whereas Plan doesn't have that problem, because you can always buy Plan when Market square is in your hand.
To a certain degree, a great many of the suggestions in this thread really represent basic synergies, and almost all of them have multiple possible replacements for one or more of the cards.
In a way, this observation simply belongs in the Market Square wiki article: It's a card that like self-trashers, some self-trashers are events such as Plan and Trade, eliminating the need for matching. If you're using it with a trashing action, refer to the article on...um...matchers? Is Dominion missing a term?
Is there a list of cards/strategies somewhere that can effectively get cards to meet up in the same hand without shuffle luck? I'm thinking this needs a separate thread. I'll go make one now.
I noticed this combo on a board a day or two ago and decided to go for it. I ended up winning on turn 14.
I think this combo is a little bit stronger than just MS+self-trasher for a couple of reasons. Firstly, you are more focused on trashing than the reaction, so you buy MS and trash even when you don't have MS in hand to gain gold with. Also, if you draw into double gold and MS, you buy two MS and trash two cards in hand even if you only gain one or zero gold for it. By the time you purchase the last MS, you'll probably gain three gold that turn if you want to. Then you green.
To double province each turn, you'll need to add a money-cantrip (I picked up a single conspirator), but even at one province per turn, you'll probably do alright. Maybe pick up Province/Duchy one turn if your opponent is working fast, too.
The fact that MS cost 3 and gives you a treasure producing 3 is excellent because you really just want to trash as quickly as possible, and this quality makes double trashing much easier.
Lastly, Plan is better than self-trashers in general because you only buy it once and get the effect multiple times, unlike Trade, Embargo, Raze, Pillage, etc.
In the game I played, my opponent didn't contest the MS pile, so I may have gotten a little lucky, but I still think this a very good combo.