Well, you'll never need more than $k-1$ extra dimensions. Let $\hat{v}_1 = v_1 \oplus (1,0,\ldots, 0)$, $\hat{v}_2 = v_2 \oplus (a,1,0,\ldots,0)$, $\hat{v}_3 = v_3 \oplus (b,c,1,0,\ldots, 0)$, etc., and choose $a, b, c, \ldots$ to ensure orthogonality. But this does not tell us under what conditions we can get by with fewer extra dimensions.

If we write $\hat{v}_i = v_i \oplus w_i$ then we have $\langle \hat{v}_i, \hat{v}_j\rangle = \langle v_i, v_j\rangle + \langle w_i, w_j\rangle$. So the problem is to find vectors $w_i$ which span as low dimensional a space as possible, such that $\langle w_i, w_j\rangle = -\langle v_i, v_j\rangle$ for all $i$ and $j$. This can be expressed by saying that the Gramian matrix of the $w_i$'s is minus the Gramian matrix of the $v_i$'s, except on the diagonal (where it can be anything, we don't care).

I think the dimension of the space spanned by the $w_i$'s equals the rank of their Gramian matrix --- if so, then the problem is to fill in the diagonal entries in a way that (1) minimizes rank while (2) keeping the matrix positive semidefinite. Any positive semidefinite matrix is the Gramian matrix of some family of vectors, so solving (1) and (2) will give us the vectors $w_i$. In some sense that answers the question, but it is not a very explicit answer.

Well, you'll never need more than $k-1$ extra dimensions. Let $\hat{v}_1 = v_1 \oplus (1,0,\ldots, 0)$, $\hat{v}_2 = v_2 \oplus (a,1,0,\ldots,0)$, $\hat{v}_3 = v_3 \oplus (b,c,1,0,\ldots, 0)$, etc., and choose $a, b, c, \ldots$ to ensure orthogonality. But this does not tell us under what conditions we can get by with fewer extra dimensions.

If we write $\hat{v}_i = v_i \oplus w_i$ then we have $\langle \hat{v}_i, \hat{v}_j\rangle = \langle v_i, v_j\rangle + \langle w_i, w_j\rangle$. So the problem is to find vectors $w_i$ which span as low dimensional a space as possible, such that $\langle w_i, w_j\rangle = -\langle v_i, v_j\rangle$ for all distinct $i$ and $j$. This can be expressed by saying that the Gramian matrix of the $w_i$'s is minus the Gramian matrix of the $v_i$'s, except on the diagonal (where it can be anything, we don't care).

I think the dimension of the space spanned by the $w_i$'s equals the rank of their Gramian matrix --- if so, then the problem is to fill in the diagonal entries in a way that (1) minimizes rank while (2) keeping the matrix positive semidefinite. Any positive semidefinite matrix is the Gramian matrix of some family of vectors, so solving (1) and (2) will give us the vectors $w_i$. In some sense that answers the question, but it is not a very explicit answer.