「食べ始める」と「食べだす」は、ほとんど同じ意味だと思います。ただ、「食べだす」の方は「急に食べ始める」ようなニュアンスがあるので、「さあ、食べ始めましょう。(Let's start eating)」は自然ですが、「さあ、食べだしましょう」は、不自然です。
「彼女は泣き出した」は、突然泣き出したようなニュアンス、あるいは、彼女が泣くことを書き手が予想していなかったようなニュアンスがありますが、「彼女は泣き始めた」というと、突然泣き始めたかどうかは不明です。
「言い出す」は使えても、「言い始める」ではおかしい文脈や文型もあります。例えば・・・
「変なことを言い出さないでくれよ。」とは言いますが、「変なことを言い始めないでくれよ。」とは普通は言いません。
「妻が急に、離婚したいと言い出した。」とは言いますが、「妻が急に、離婚したいと言い始めた。」はちょっと変です。
(「言い出しっぺ」という言葉はありますが、「言い始めっぺ」はありませんね。)