sim[m_] := NestWhileList[
  Mod[RandomChoice[# + {1, -1}], m + 1] &, 0, Union[{##}] != Range[0, m] &, All]

With[{k = 1000, n = 10},
 Table[{m, Table[Length[sim[m]] - 1, k] // Mean // N}, {m, 2, n}]]

(* {{2, 2.999}, {3, 6.007}, {4, 9.994}, {5, 14.953}, {6, 21.18},
    {7, 27.07}, {8, 34.993}, {9, 44.029}, {10, 55.108}} *)