Define $$g=\gcd(2^{k+3}-1,-2×(2^{k+1}-1)).$$
Then we know that there exist some integers $r$ and $s$ such that $$g=r×(2^{k+3}-1)-(2×s)(2^{k+1}-1).$$
Then my question is: Can we find an explicit formula for $r$ and $s$ as a function of $k$?
I remark that if $k$ is odd then $g=3$ and if $k$ is even, then $g=1$. So, the problem is reduced to how one can represent $1$ or $3$ in the above form.
Just looking to cancel some high powers of $2$, we start with the observation that $$ (2^{k+3}-1) + 2\bigl( -2(2^{k+1}-1) \bigr) = 3. $$ This already gives the answer $(r,s)=(1,2)$ when $k$ is odd. Otherwise, we just want to subtract $3$ many times from $2^{k+3}-1$ until the answer is $1$. Of course $$ 2^{k+3}-1 = 3\frac{(2^{k+3}-1)-1}3 + 1 $$ (where the fraction is an integer when $k$ is even). Therefore \begin{align*} 1 &= (2^{k+3}-1) - \frac{2^{k+3}-2}3\cdot3 \\ &= (2^{k+3}-1) - \frac{2^{k+3}-2}3 \Bigl( (2^{k+3}-1) + 2\bigl( -2(2^{k+1}-1) \bigr) \Bigr) \\ &= - \frac{2^{k+3}-5}3 (2^{k+3}-1) - \frac{2^{k+4}-4}3 \bigl( -2(2^{k+1}-1) \bigr), \end{align*} so that the answer is $(r,s) = \biggl( - \dfrac{2^{k+3}-5}3, - \dfrac{2^{k+4}-4}3 \biggr)$ when $k$ is even. (Of course there are many answers in both cases, but these are the ones with the smallest numbers.)
Note that the above computations are precisely the usual Euclidean algorithm! It just looks funnier when the numbers are symbolic (and might have to split into cases based on congruence classes, as we saw).