Although many problems that we now reduce to polynomial equations were solved since time immemorial early occurences are coached in verbal and/or geometric terms, and polynomials are not treated as separate items. For early occurences of geometric problems that lead (today) to quadratic equations see The origin of quadratic equation in actual practice. The equations proper, let alone polynomials themselves, do appear only relatively late.
The first breakthrough was made by Diophantus in Arithmetica (c.250 AD), who introduced notation for an indeterminate $\varsigma$, the first $x$, and its powers up to sixth, $\Delta^{\upsilon}$ is $\varsigma$ squared, $K^{\upsilon}$ cubed, etc. So for the first time it became possible to write down polynomials, albeit only up to degree six. He even had symbols for constant terms and reciprocals of powers. Diophantus was also first to convert text problems into polynomial equations, and use some rudimentary (verbal) algebra to solve them. However, Diophantus's "polynomials" are not yet separate items either, they only appear as sides in equations. This is analogous to Babylonian and Hellenistic use of zero symbol as a placeholder. Here is $3x^2+1-(10x^3+2x)=4$ in Diophantus's notation: $\Delta^{\upsilon}\gamma\mathring{M}\alpha\pitchfork K^{\upsilon}\iota\varsigma\beta\iota^{\sigma}\mathring{M}\delta$. See Hettle's The Symbolic and Mathematical Influence of Diophantus's Arithmetica for details and notation.
The next great step was made by medieval Islamic mathematicians. The familiar rules of algebra were formalized by Al-Khowarizmi (ca. 800-847 AD), who also derived first algebraic solutions to linear and quadratic equations (before him they were either given as prescriptions, or geometrically concealed as in Euclid). Perhaps the first person to conceive of general polynomials is Al-Karaji (953-1029 AD), who can be called their "discoverer". He realized that the series of powers (and their reciprocals) extends indefinitely. Correspondingly, he extended Diophantus's notation to write polynomials of arbitrary degree, and gave rules for their addition, subtraction and multiplication.
But polynomials truly come to shine in the work of Al-Samawal (1130-1180) The Shining Book on Calculation. He dispensed with verbal and semi-verbal notation, and used tables of coefficients to write and perform calculations with polynomials, including those with negative powers (Laurent polynomials). This greatly simplified all algebraic calculations with them because "laws of exponents" are applied automatically. And he gives the first polynomial division algorithm, the grandfather of modern long and synthetic division. He also noted the analogy between his way of writing polynomials and the decimal positional notation, and transferred his algorithms to decimal numbers by replacing the variable with $10$. This was the first mathematical justification of a positional division algorithm. See Islamic Mathematics and Katz's History of Mathematics.
Unfortunately, Renaissence Europe did not absorb Al-Samawal's innovations, and instead proceeded through incremental improvement of notation. In particular, the notation used by del Ferro, Tartaglia and even Cardano to solve the cubic in 1500s was largely verbal, and inferior to Al-Samawal. Even so, in Ars Magna (1545) Cardano introduced the technique of substitutions that not only solved the cubic and quartic, but became indispensable in polynomial algebra later. See Why is "Cardano's Formula" (wrongly) attributed to him?
Viète's Isagoge (1591) introduced modern style symbolic notation and algebraic manipulation rules Viète still uses words for powers, these were symbolized by Descartes, but they are attached to variables. In particular the use of letters for parameters allowed general consideration of polynomials rather than example by example. And philosophically, in Viète's works we for the first time encounter a systematic use of the method where problems are converted to equations, and then solved algebraically. See Viète's Relevance and his Connection to Euler, and references therein.
This method was further sharpened by Descartes's analytic geometry in La Géométrie (1637). He connected it to the classical method of analysis and synthesis described by Pappus, but with conversion to algebraic equations in the middle. This not only streamlined solutions of many classical problems, but also covered many new ones, expressible by higher order equations. Moreover, Descartes considers polynomials in two variables, which represented algebraic curves in analytic geometry, and this is where algebraic geometry takes its root. Descartes's formalization of construction methods, and classification of problems based on their algebraic representation, led to techniques required for impossibility proofs, starting with Gregory's (unsuccessful) attempt to prove algebraic unsolvability of quadrature (1667). See Crippa's Impossibility Results: from Geometry to Analysis.
