Let me estimate the number $N_k$ of such bases for a fixed $k$. Aside remark. The number of bases for $k=k_0$ equals the number of those for $k=n-k_0$, as the bijection $(\beta_0,\dots,\beta_{n-1})\to (\beta_{n-1},\dots,\beta_{k_0},h^{-1}\beta_{k_0-1},\dots,h^{-1}\beta_0)$$ shows.
So let us fix any $k$. The first $k$ elements can be chosen in $\prod_{i=0}^{k-1}(q^n-q^i)$ many ways. Each next element $\beta_i$ should lie outside $V_i=\langle \beta_0,\dots,\beta_{i-1}\rangle$, as well as outside $V_i'=\langle h^{-1}\beta_0,\dots,h^{-1}\beta_{k-1},\beta_k,\dots,\beta_{i-1}\rangle$. If $d_i=\dim(V_i\cap V_i')$, then $\beta_i$ can be chosen in $q^n-2q^i+q^{d_i}$ many ways; notice that $i\geq d_i\geq \max(i-k,2i-n)$. Thus $$ N_k\geq \prod_{i=0}^{k-1}(q^n-q^i)\prod_{i=k}^{n-1}(q^n-2q^i+q^{\max(i-k,2i-n)}). $$
This estimate can be improved by noticing that $d_i\geq d_{i-1}+1$. So, e.g., for $k=1$, if we choose $\beta_1=(h^{-1}+1)\beta_0$, then $V_2=V_2'$, so $d_i=i$ for $i\geq 2$. But it seems appropriate to choose large $k$...
Notice that for $k=n-1$, the estimate gives $$ N_{n-1}\geq (q^n-2q^{n-1}+q^{n-2}).\prod_{i=0}^{n-2}(q^n-q^i), $$ which is $1-\frac1q$ of all bases. Do you need much sharper bounds?