You may always assume that $f$ starts with a zero. For each $i = 1,\ldots, n-k+1$, let $S_i$ be the set of strings whose the substring from position $i$ to position $i+k-1$ is equal to $f$. It is trivial that $|S_i| = 2^{n-k}$. The set of strings whose have a substring equal to $f$ is the union of these sets. Therefore, one has the inequality
$$M_n(k) \le (n-k+1)\cdot 2^{n-k}$$
where $M_n(k) = \max Q_n(f)$, and $Q_n(f)$ denotes the number of strings whose have a substring equal to $f$.
Moreover, note that $S_{ij} = S_i \cap S_j$ has the same cardinality $2^{n-2k}$ when $|i - j| \ge k$, and is empty for all $i, j$ such that $|i-j| < k$ if and only if $f$ is not invariant under any translations. (A string is invariant under some translation if any only if it is decomposable (i.e., $f = g \ldots g$ for some string $g$.) Therefore, one can see that $Q_n(f)$ is maximum when $f$ is not invariant under any translations, e.g. $f = 0\ldots 01$. The formula for $M_n(k)$ is possible given that one write $n = k d + r$, and then find out exactly how many $S_I = \cap_{i\in I} S_i$ is non-empty. But for the purpose of proving the inequality the question ask the rough bound above is enough.
Now, $S_{ij}$ has maximum cardinality (the same as being non-empty) for all $|i-j| < k$ if and only if $f$ is invariant under any translations. In other words, $f = 0\ldots 0$. Note that if $S_{ij}$ is empty for some $|i-j| < k$, then it is non-empty for quite a few more, and the $S_{ijk}$ cannot recover much, thus the minimum value of $Q_n(f)$ is obtained at $m_n(k) = Q_n(0\ldots 0).$
Now the $m_n(k)$ follows the following recursive formulas:
For $n = k + i$, with $1\le i \le k-1$, we have
$$m_{k+i}(k) = m_{k+i-1}(k) + \cdots + m_k(k) + 2^{n-k}.$$
The reason for this recursive formula is that if the last entry of your string is $1$, then you have $m_{k+i-1}$ of the strings, if then the last two entries of your string is $10$, then you have $m_{k+i-1}$, etc, until if the last $i$ entries is $0\cdots 0$, then its last $k$ entries must all be zero, thus the factor of $2^{n-k}$ at the end.
From this recursive formula one deduces that
$$m_{k+i} = i\cdot 2^{i-1} + 2^i$$
for $i= 0, \ldots, k-1$.
For $i \ge k$, similarly one has the formula
$$m_{k+i} = m_{k+i-1} + \cdots + m_{i+1} + 2^i.$$
In particular, $m_{2k} = k\cdot 2^{k-1} + 2^k - 1$ and $m_{k +i} > i\cdot 2^{i-1}$. (Each of the term in the recursive formula for $m_{k+i}$ is larger than $2^i$ (it is actually much larger).
To prove your inequality, obviously from the explicit formula, it is true when $n \le 2k$. And for $i > k$, it follows from the previous inequality $i\cdot 2^{i-1} < m_{k+i}.$
