One element of a transcendence basis can be exchanged for a suitable rival

Because $T$ is a transcendence basis, $K$ is algebraic over $k(T)$; in particular $s$ is algebraic over $k(T)$. Choose a finite subset $U=\{t_1,\dots ,t_m\}\subseteq T$ of minimal size such that $s$ is algebraic over $k(U)$.

Minimality forces $m\ge 1$. Choose a nonzero polynomial relation for $s$ over $k(U)$ and clear denominators to obtain $P(s,t_1,\dots ,t_m)=0$ with $P\in k[X,Y_1,\dots ,Y_m]$ nonzero. The variable $Y_m$ must occur in $P$; otherwise the same relation would show that $s$ is algebraic over $k(t_1,\dots ,t_{m-1})$, contradicting minimality of $U$. Therefore, viewing $P$ as a polynomial in $Y_m$ over $k(s,t_1,\dots ,t_{m-1})$, we see that $t_m$ is algebraic over $k(s,t_1,\dots ,t_{m-1})$.

Put $T^{\mathrm{\prime }}=(T\setminus \{t_m\})\cup \{s\}$. If $T^{\mathrm{\prime }}$ were algebraically dependent, then $s$ would be algebraic over $k(T\setminus \{t_m\})$. Together with step 2.1 this would make $t_m$ algebraic over $k(T\setminus \{t_m\})$, contradicting algebraic independence of $T$. Hence $T^{\mathrm{\prime }}$ is algebraically independent.

Step 2.1 shows that $t_m$ is algebraic over $k(T^{\mathrm{\prime }})$, so $k(T)$ is algebraic over $k(T^{\mathrm{\prime }})$. Since $K$ is algebraic over $k(T)$, it is also algebraic over $k(T^{\mathrm{\prime }})$. By [L1], $T^{\mathrm{\prime }}$ is a transcendence basis of $K$ over $k$.