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. 1 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 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}}.$$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$.