If every polynomial in $k[x]$ has a root in $E$, is $E$ algebraically closed?

This is true, but it is not trivial. See Gilmer, A Note on the Algebraic Closure of a Field.

The OP asked for another reference in the comments. A google search reveals Richman A theorem of Gilmer and the canonical universal splitting ring, which apparently gives a constructive proof. In this Math Stackexchange answer, Martin Brandenburg gives as an additional reference Isaacs Roots of Polynomials in Algebraic Extensions of Fields.

Isaacs proves a generalization of Gilmer's theorem: An algebraic extension $K$ of a field $k$ is determined up to isomorphism over $k$ by the set of polynomials in $k[x]$ which have a root in $K$. He cites Gilmer and p.88 of a book called Theory of Fields by Nagata. It's not clear to me that such a book exists, but I did track down a proof of Gilmer's theorem as Theorem 2.12.2 on p. 71 of Nagata's Theory of Commutative Fields. Regarding Gilmer's theorem, Isaacs writes:

This theorem is not quite the triviality it may appear to be at first glance. If one knows that all polynomials in $F[X]$ split over $E$, then it is an easy exercise to show that $E$ is algebraically closed. Under the weaker hypothesis of Theorem 1, however, this conclusion is considerably more difficult to prove. (It is more difficult to find in the literature, too. A search of about a dozen books that deal with field extensions was able to uncover only one proof of this result and two cases where at least a part of Theorem 1 appears as a problem.)

Let $E/k$ be an algebraic extension such that $E$ contains a root of every polynomial $\in k[x]$.

$E = \overline{k}$.

• If $k$ is finite or of characteristic zero then the claim is obvious with the primitive element theorem : for any $f \in k[x]$, all its roots are contained in a simple extension $k[a] $ thus in $\sigma(k[a]) = k[\sigma(a)]$ for any root $\sigma(a)$ of $a$'s minimal polynomial.

• Otherwise we have $char(k) = p$. For each $a$ let $a^{1/p^r}$ be the unique root of $x^{p^r}-a$. Thus it makes sense to mention the field $k^{1/p^r}$ which is contained in $E$.

  For any $c \in \overline{k}$, let $g \in k[x]$ be its minimal polynomial, let $p^r$ be the largest $p$-th power such that $g(x) = h(x^{p^r})$, then $h \in k[x]$ is irreducible and it is not of the form $h(x) = H(x^p)$ thus $h' \ne 0$ which implies $h$ is separable (if $h$ was inseparable then $\gcd(h,h')$ would divide it). As $h(c^{p^r}) = g(c) = 0$ then $c^{p^r}$ is separable and we can use the primitive element theorem to get $a$ such that $k[a]$ contains all the conjugates of $c^{p^r}$. For any $\sigma \in Aut(\overline{k}/k)$, $k[\sigma(a)]$ contains all the conjugates of $c^{p^r}$, in particular $c^{p^r} = \sum_{j=0}^J u_{j, \sigma}\sigma(a)^j, u_{j, \sigma} \in k$.

  $E$ contains $k^{1/p^r}$ and one root $ \sigma(a)^{1/p^r}$ of $a^{1/p^r}$'s minimal polynomial, hence $E$ contains $\sum_{j=0}^J u_{j, \sigma}^{1/p^r}(\sigma(a)^{1/p^r})^j$, a root of $x^{p^r}-c^{p^r}$ which has to be $c$.