Exact definition of algebraic set

I don't think you need you should need to use the nullstellensatz to prove these two definitions are equivalent.

Given sets in $k^n$ the Zariski topology meaning the closed sets $Z$ are exactly the vanishing locus of some set of polynomials $V(I)$ i.e. an algebraic set according to your second definition. Notice that we can take $I$ to be an ideal because for any set of polynomials $H \subset k[x_1, \dots, x_n]$ we have $V(H) = V((H))$ where $(H)$ is the ideal generated by $H$.

Now I claim that for any set $S \subset k^n$ the following formula holds, $$ V(I(S)) = \overline{S} $$ where $\overline{S}$ is the closure of $S$ in the Zariski topology. Let's prove this. By definition, $V(I(S))$ is closed and $V(I(S)) \supset S$ so $V(I(S)) \supset \overline{S}$. Conversely, let $C$ be a Zariski closed subset containing $S$. Then, $C = V(T)$ and $S \subset V(T)$ means by definition that every $f \in T$ vanishes on $S$ so $T \subset I(S)$. Therefore, $$ V(I(S)) \subset V(T) = C $$ because if $x \in V(I(S))$ then every $f \in I(S)$ has $f(x) = 0$ and in particular for $f \in T \subset I(S)$ we have $f(x) = 0$ so $x \in V(T) = C$. Therefore, $V(I(S)) \subset \overline{S}$ because it is contained in every Zariski closed set containing $S$.

Now this formula immediately implies what you want. Indeed, let $S$ be Zariski-closed or equivalently an algebraic set according to the second definition. Then $\overline{S} = S$ so, $$ V(I(S)) = S $$ proving that $S$ is algebraic according to the first definition.

This does not even require that the field is algebraically closed while the correspondence you cite (using the nullstellensatz) most certainly does.