If I understand the question correctly, brute-force search with some Julia code gives following small values

\begin{array}{rr|rrrrrrrrrrrrrrrrr}
&& n\\
&& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\
\hline
m & 2 & 4 & = \\
  & 3 &  & 7 & 8 & = \\
  & 4 &  &   & 11 & 13 & 14 & 15 & 16 & = \\
  & 5 &  &   &    & 16 & 19 & 21 & 23 & 25 & 27 & 30 & 31 & 32 \\
  & 6 &  &   &    &    & 22 & 26 & 29 & 32 & 35 & 38 & 41 & 45 \\
  & 7 &  &   &    &    &    & 29 & 34 & 38 & 42 & 46 \\
  & 8 &  &   &    &    &    &    & 37 & 43 & 48      \\
  & 9 &  &   &    &    &	&    &    & 46 & 53      \\
\end{array}

"=" means that the rest of the row repeats the last value, that is, there is a string that exhibits all $2^m$ subsets (adding more length will not change this).

The main diagonal is as described in the question. The first superdiagonal is 4,8,13,19,26,35,43,53 which has [two OEIS matches][1], the first being A034856 "a(n) = binomial(n+1, 2) + n - 1 = n*(n + 3)/2 - 1".

If we write $T(m)$ for the smallest $n$ where $2^m$ appears, $T$ forms a sequence that starts 1,2,4,8,13, which matches many things in OEIS. Examples of shortest strings where all $2^m$ subsets of alphabet ${0,1,\ldots,m-1}$ appear are:

\begin{array}{l|l}
m & T(m) \\
\hline
1 & 1 & 0 \\
2 & 2 & 01 \\
3 & 4 & 0120 \\
4 & 8 & 01203123 \\
5 & 13 & 0123401302413
\end{array}


  [1]: https://oeis.org/search?q=4%2C8%2C13%2C19%2C26%2C34%2C43%2C53&sort=&language=&go=Search