Show that $n^2+n$ is even for all $n\in\mathbb{N}$ by contradiction

You can't choose $k$ here; you have to show it's true for all of them. I would prove it this way. Assume $n^2+n$ is odd. This means $n(n+1)$ is odd, but that's impossible, because a number and its successor can't both be odd.

I hate to be the bearer of bad tidings, but the presented proof attempt is flawed. There is no guarantee that any $k$ corresponds to a given $n^2 + n$, so the assumption that

$\forall n \in \Bbb N, \exists k \in \Bbb Z, \; n^2 + n = 2k + 1 \tag 1$

is erroneous.

I prove it like this: if $n$ is odd, then $n + 1$ is even; so whether $n$ is odd or even, we have $2 \mid n(n + 1)$, i.e., $n(n + 1)$ is even.

Suppose $n^2 + n$ is odd for all natural numbers $n$. Then $n(n+1)$, the product of two consecutive integers, is also odd. However, an odd number can not have any even factors. Either $n$ is odd, and $n+1$ is even, or $n$ is even and $n+1$ is odd, as they are consecutive integers. The product $n(n+1)$ has one even and one odd factor, which contradicts our previous statement that $n(n+1)$ is odd, as an odd number times an even number is an even number.