Be'er Hataiv 426:10 says that one can say Kiddush Levana as early as 3 days after the Molad. The Rambam - Hilchos Brachos 10:17 rules that one may say Kiddush Levana immediately after the Molad. Suppose 2 days after the Molad one made Kiddush Levana, and then realized he did it too early. Should he say Kiddush Levana again with a Bracha? (sources)
The Be'er Hetev that you quote says that if Saturday night is before the third of the month, Kiddush Levana should be pushed off to the next Saturday night because it will still be before the 11th of the month (and we don't usually push off Kiddush Levana to Saturday night if it will be after the 11th of the month for fear of a few days of clouds).
But he doesn't say we push it off because you can't say it then.
Indeed his source is the Magen Avraham who quotes a number of Rishonim who permit saying it on Rosh Chodesh and one who even says doing so is a Mitzva min haMuvchar. (See Rashi, Semag, Rambam, Sefer haKaneh, Meiri, Tashbetz, Maharam Rikanti, Yad Ramah, Sefer HaPardes, etc. and note the Girsa of בחידושה in the Rif and Yerushalmi. Indeed the Bavli, which defines explicitly the last time one can say it, omits any mention of an earlier limitation and in one manuscript actually calls it "the Beracha on Rosh Chodesh".)
Thus it seems according to this majority opinion, he has fulfilled his obligation in the case you describe and need not say it again.
Indeed the first Rishon who suggests waiting at all before saying Kiddush Levana (with the exception of certain Kabbalistic positions of waiting a week) is Rabbeinu Yonah (Berachot R21a) who offers an original read of a variant text of Masekhet Soferim 20:1 that would require waiting "two or three days" until one can benefit from the light. While the Peri Megadim (OC 426 EA 13) thinks that this means 72 hours (!וצע"ג), the straightforward understanding of "two or three days" is that it's an approximation (perhaps because the Molad is not always at the same time of day). Thus while the Bach (OC 426) writes that the longstanding tradition is not to wait a week but to say Kiddush Levana soon after three days, his son-in-law the Taz (ibid. sk 3) writes about his position that "it is not about days but from the time that one can benefit from [the moon's] light, which is certainly [the case] after 3 days". The case of the OP is almost certainly such a case as the moon probably looked regular enough to him that he didn't get concerned.
Thus even according to this minority opinion, which many are generally careful for because it doesn't limit their Saturday night opportunities (see above), he has fulfilled his obligation and need not say it again.
(To be fair, Rav Saadya Gaon's siddur (p 90) says Kiddush Levana is said on nights 4-14 (inclusive) of the month, but this is not quoted in later works, it's not even clear that's an authentic wording (see footnotes there), and there are other reasons why the positions there appear non-standard.)
Rav Moshe Feinstein (Igrot Moshe OC 1:143) explains that according to the Shulchan Arukh, Kiddush Levana should Lekhatchila be said on Rosh Chodesh, and only if that is unfeasible (very common) then it is better to wait until the moon brightens significantly before reciting it. He also writes (ibid. CM 2:47:2) that waiting any time for the moon to brighten is רק הידורא בעלמא a mere beautification of the Mitzva [but not an essential component]. According to that, it seems he has fulfilled his obligation in the case you describe and need not say it again
Rav Shlomo Zalman Auerbach rules (Halikhot Shelomo Rosh Chodesh 1:108) that one who recited Kiddush Levana before the third of the month has fulfilled his obligation.