A simple approach is to overdo it a little and show that $n$-qubit Pauli operators form an *orthogonal* basis in a real vector space $L_H(\mathbb{C}^{2^n})$ of $n$-qubit Hermitian operators with appropriately defined inner product. To that end, we first show that $\langle A,B\rangle_{HS}:=\mathrm{tr}(A^\dagger B)$ defines an inner product$^1$. Next, we show that for any two Pauli operators $W:=W_1\otimes\dots\otimes W_n$ and $W':=W'_1\otimes\dots\otimes W'_n$ we have $\langle W,W'\rangle_{HS}=0$ if and only if $W\ne W'$. This implies$^2$ linear independence. Now, there are exactly $4^n$ Pauli operators in $L_H(\mathbb{C}^{2^n})$. However$^3$, $\dim L_H(\mathbb{C}^k)=k^2$, so Pauli operators span $L_H(\mathbb{C}^{2^n})$.

---
<sup>$^1$ The function $\langle .,.\rangle_{HS}$ is known as the Hilbert-Schmidt inner product.\
$^2$ Because the coefficient in front of $W_k$ in a linear combination $A$ is proportional to $\langle W_k,A\rangle_{HS}$.\
$^3$ There is a linear bijection between $L_H(\mathbb{C}^k)$ and $\mathbb{R}^{k^2}$.
</sup>