From what I've read about them, the only difference is that 〜だす implies a more sudden and abrupt start than does はじめる.
帰っていた途中、思わず走り始めた。
信号で選手はみんな走り出した。
I'll admit that those sentences are perhaps not the most natural, but I hope it gets the message across. Also, I'd like to know if there are any more differences.