I'll try to answer the question of when the prohibition on kitniyot is first attested in the historical record. In contrast to modern-day practice among more Orthodox and Orthodox-leaning Ashkenazim, the sages of the Talmudic era are generally quite permissive of eating rice and other kitniyot during Pesach, cf. Pesachim 35a:

The Gemara asks: From where are these matters, that matza cannot be prepared from rice or millet, derived? Rabbi Shimon ben Lakish said, and likewise a Sage of the school of Rabbi Yishmael taught, and likewise a Sage of the school of Rabbi Eliezer ben Ya’akov taught that the verse states: “You shall eat no leavened bread with it; seven days you shall eat with it matza, the bread of affliction” (Deuteronomy 16:3). This verse indicates that only with substances which will come to a state of leavening, a person fulfills his obligation to eat matza with them, provided he prevents them from becoming leavened. This excludes these foods, i.e., rice, millet, and similar grains, which, even if flour is prepared from them and water is added to their flour, do not come to a state of leavening but to a state of decay [siraḥon].

The minority opinion presented by Rabbi Yochanan ben Nuri is that rice must be prohibited, as it is "close to being leavened," but the majority of sages do not claim the similarity between rice and chametz that is often purported as the logical basis for the prohibition on kitniyot during Pesach. So when does the general prohibition date from?

In 2016, the Committee on Jewish Law and Standards released a legal decision permitting Conservative Jews to eat kitniyot during Pesach. From the history detailed in the opinion published by the CJLS:

In early medieval Ashkenaz [Germany/France and the surrounding territories] the custom of avoiding kitniyot seemed to have aroused some debate. The most sustained discussion of this can be found in the comments of Rabbeinu Peretz (France, 13th c.) to the Sefer Mitzvot Katan of his teacher Isaac of Corbeil, Mitzvah 2222. He writes as follows:

Concerning kitniyot… our rabbis customarily prohibit altogether eating them on Pesah…. But many great sages permit them. My teacher Rabbenu Yehiel would eat the white bean called “favas” and said [that he did] so in the name of great sages. And he cited as proof that even rice [n.b. about which the Talmud briefly considers if it might also be a grain fit as matzah and hametz] … the Talmud said no one considers this [to be true] … Nevertheless, it is very difficult to permit a thing that everyone since the earliest sages treats as prohibited (for surely they did not prohibit is as true hametz, for they did not err in a matter clear to the most elementary student of the law, for it is there in Pesahim that nothing becomes hametz save the five species). Therefore it appears that we should support the custom and prohibit all kitniyot on Pesah, not as true hametz, for that is an error, but as a decree because kitniyot are cooked, as grain is cooked, in a porridge, and were we to permit kitniyot [people] might come to substitute and permit [grain-based] porridge… and it is something grain-like (midi d’midgan) like the five species, as it says in chapter HaSokher et haPoalim [n.b. Bava Metzia 87a where bread of kitniyot flour is considered]…, and there are places that regularly make bread of them just like from the five species [of grain] and [people] might come to substitute, for they are not Torah-learned. [Kitniyot] are not similar to vegetables… that do not resemble grain at all and will not be substituted. It is [therefore] a fit custom to refrain from all kitniyot, as I explained… Even though the Talmud permitted rice, this was specifically in their day when all were fluent in the laws of prohibition and permission, but in these latter generations it is clear that one should be restrictive, as I have said.

A responsum prepared by Rabbi David Golinkin for the Va'ad Halakhah of the Rabbinical Assembly of Israel in 1989 details the many historical rulings on kitniyot during Pesach up to this point and finds a large body of rabbinical opinions from 12th- and early 13th-century Ashkenaz that rule permissively. The first opinions of a prohibitive nature crop up around the same time as the commentary of Rabbeinu Peretz. From Golinkin:

In 13th century France we hear for the first time of the custom of prohibiting rice and kitniyot on Pesaḥ. This custom was expressed in three different ways:

A. “Not to eat zeronim [i.e., humus] on Pesaḥ”. So wrote Rabbi Asher of Lunel in his Sefer Haminhagot, written in Provence ca. 1210 (he is quoted by Rabbeinu Manoaḥ on the Rambam, Ḥametz Umatzah, 5:1).

B. To use kitniyot only by halitah, i.e., to put them in water that is already boiling, because even the five species of grain can be eaten in this manner (Pesaḥim 39b and Rambam, Ḥametz Umatzah, 5:3). This custom was related by Rabbi Samuel of Falaise (in Or Zarua, part 2, fol. 58c) and also by Rabbeinu Peretz (in Hagahot Semak, paragraph 222). The second description is particularly interesting: “And it seems to me that I heard [from our Master and Rabbi, Yosef Shliah Tzibbur of Troyes (13th century) in the name of his mother, the daughter of Rabbeinu Baruch (late 12th century)] about the beans that should not be cooked on Pesaḥ other than in boiling water from the moment they are added to a pot”.

C. Rabbeinu Peretz also reports about another custom – a general prohibition on kitniyot: “and on kitniyot such as fèves [white beans] and beans and rice and lentils and the like, our rabbis are accustomed not to eat them at all on Pesaḥ.” Later on he claims that this it is something “that the world has been accustomed to prohibit from the days of the early Sages.” A similar custom is mentioned by Rabbi Aharon Hakohen of Lunel (Provence, early 14th century, in Sefer Orḥot Ḥayyim, Hilkhot Ḥametz Umatzah, paragraph 55) in the name of Rabbi Shemuel bar Mordechai z"l (Provence, ca. 1300): “And the early ones were accustomed [on Pesah] not to eat a cooked dish made from types of kitniyot ever.” And Rabbi Mordechai ben Hillel Ashkenazi relates (in the Mordechai on Pesaḥim, Chapter 2, paragraph 588): “And Rabbeinu Barukh and Rabbeinu [Shemuel] of Evreux (13th century) did not eat types of kitniyot on Pesaḥ”.

However, as we have seen, there is no proof that this is a custom of the “early Sages”. Moreover, already in the 13th century, the Rishonim did not know how to explain these customs. Rabbeinu Peretz himself stresses that there is no prohibition involved: “Obviously [mistama] they did not treat this custom as a prohibition due to concern over actual leavening, as they did not err in a matter that school children who studied the halakhah know, that it says explicitly in Pesahim that only the five species of grain can become hametz."

(See the responsum of Golinkin for the history of the various apologetics concerning the contemporary prohibition of kitniyot, as well as many other relevant historical details to the evolution and spread of the prohibition.)