The "four elements" are the four elements of the Ancient Greeks. These are quite old but are most popularly known through the work of Aristotle, who came up with a cosmology that linked the elements, the humors, physical properties like motion (fire moves up, water moves down), and qualities (hot/wet/dry/cold). This formed the backbone of Aristotle's theory of matter, and was essentially "required reading" in the West until the 18th century or so, when it became very clear (in what we today call the Chemical Revolution) that the theory of matter was so inadequate as to not even be considered a starting point for thinking about what elements actually make up the world.

So it is in some way not surprising that such notions have become far more diffuse and remained a part of a popular culture of sorts, even though practically nobody reads Aristotle's work on matter anymore.

I have no idea re: China, much less Naruto.