The reason why the weight needs to be $k=2$ becomes clear when you consider this (equivalent) version of modularity: $E/\mathbb{Q}$ is modular if there there exists a normalized newform $f$ for $\Gamma_0(N)$ such that $L(f,s) = L(E,s)$, i.e., the $L$-function attached to $f$ coincides with the Hasse-Weil $L$-function attached to $E/\mathbb{Q}$.
Now, the $L$-function of a normalized newform of weight $k$ for $\Gamma_0(N)$ has an Euler product of the form:
$$L(f,s) = \prod_{p|N} \frac{1}{1-\lambda_p p^{-s}} \prod_{p\nmid N} \frac{1}{1-\lambda_p p^{-s} + p^{2k-1-2s}}.$$p^{k-1-2s}}.$$
The $L$-function of $E$ is defined as an Euler product:
$$ L(E,s) = \prod_{p\geq 2}\frac{1}{L_p(p^{-s})}, $$
where $L_p(T) = 1-a_pT+pT^2$ if $E$ has good reduction at $p$, $L_p(T)= 1-T$ if $E$ has split multiplicative reduction at $p$, $L_p(T) = 1+T$ if $E$ has non-split multiplicative reduction at $p$ and $L_p(T) = 1$ if $E$ has additive reduction at $p$.
In particular, $L_p(T)=1-a_pT+pT^2$ for almost all primes (for all primes $p\nmid N(E)$). If there is any hope that these two Euler products agree, then we must have $k=2$.
