My friend and I played with Lego together.
私の友達と私は一緒にレゴで遊びました。
with の繰り返しが気になるようでしたら、こちらを使うのがオススメです。
一応今回のような場合は、with を2回使っても文法的に間違いというわけではないと思います。ただ、その場合は、with friend の方が後ろに来ます。「レゴで遊ぶ」というのをまとめて動詞だと考えるとわかりやすいと思います。
I played with Lego with my friend.
私は友達とレゴで遊びました。