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, 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}