Chazon Ish (28:8) rejects the view of the Maadanei Y"T that the mitzvah of birchas ha'mazon was only given in year 40 when Klal Yisrael was in Eiver haYarden, which is the setting of our parsha where the mitzvah appears. All mitzvos, writes the C.I., were given at Sinai (see Chagigah 6). The details may be recorded in a different context, but that has nothing to do with when the mitzvah was given.
I am surprised that the C.I. does not cite Ramban's introduction to sefer Devarim where Ramban writes explicitly that there are no new mitzvos in our sefer.
Ramban asks on himself: but there are 70+ mitzvos that in fact are first recorded in sefer Devarim?
Ramban offers two answers: 1) these new mitzvos only apply in Eretz Yisrael, so Moshe had no need to teach them earlier; 2) these were uncommon mitzvos that might not have come up earlier.
Neither of these two reasons seem relevant to birchas ha'mazon which 1) must be done in all locations 2) and comes up as frequently as we eat. The question that therefore begs itself is why Moshe waited to command or teach the mitzvah until now.
(One might have thought that eating the mon was not a satisfying meal -- va'yincha va'yarivecha"-- and therefore there was never an opportunity of "v'achalta v'savata" that required benching in the midbar. The gemara (Brachos 48), however, writes that Moshe instituted the text of the first bracha of birchas ha'mazon on the mon [see R' Shteinman's Ayeles haShachar].)
I would suggest that contrary to what we learned in elementary school, birchas ha'mazon is not a thank you to G-d for our food. It is a thank you for Eretz Yisrael. The pasuk does not say, "v'achalta v'savata u'beirachta... al ha'ochel hatovah." It says "...u'beirachta al ha'aretz ha'tovah." (See Ramban!) In the bracha of bareich aleinu, according to nusach haGR"A (see post here) we say "v'sabeinu m'tuvah" because even though you might live in America, all of our sustenance and food and parnasa comes into the world only via the brachos Hashem bestows upon Eretz Yisrael.
The Netziv in Bamidbar (20:13) has a yesod that may help us as well. The mitzvah of tefilah, which according to the Rambam is a mitzvah d'oraysa, also only first appears in our parsha as well. Why did Moshe not teach this mitzvah earlier -- did not one daven in the midbar?
The Netziv (while not asking the question in that way) writes that in the midbar, Klal Yisrael was sustained by miracles -- the mon, the be'eir, etc. Tefilah, says Netziv, does not apply when everything is running l'ma'alah min ha'tevah. Tefilah is needed only when things are running b'derech ha'teva. What makes a tree grow? Sunlight, rain, Co2, and prayer. Rashi writes (Braishis 2:5) that G-d withheld rain from creation until man was created and could pray. Prayer is part of nature -- not the supernatural.
(Parenthetically, the Netziv there quotes a Midrash that says that Hashem values the lowest member of Klal Yisrael as much as Eliyahu haNavi. It's a pli'ah -- you mean a guy who barely keeps mitzvos gets as much great as the greatest of nevi'im?! Five years ago I posted R' Bloch's hesber, but now we have a Netziv: tefilah is the great equalizer. My mitzvos are not Eliyahu's mitzvos; my learning is not his learning. But when I cry to G-d in need, my tears are as valuable as Eliyahu's tears. Human suffering is democratic -- the lowest of us cries out in pain to Hashem with as much feeling as the greatest among us.)
True, according to the Chazon Ish, birchas ha'mazon was said over the mon, but I think like tefilah, the mitzvah essentially relates to our derech ha'teva life -- what can be more natural than eating -- and challenges us to connect that to a higher value that merely stuffing our mouth. The mitzvah may have been given earlier, but it is put in the context of our parsha because on the doorstep of Eretz Yisrael, when Klal Yisrael was about to truly become engaged in building a country, with all that entailed, all through derech ha'teva, the mitzvah took on its true meaning.
R' Yehoshua Shapira, R"Y of Yeshivat Ramat Gan, writes on our parsha that if a person eats rugalach and recites al hamichyah but has no idea how and why suddenly because of rugalach he is speaking in the bracha about Yerushalayim, about the mikdash, "mechonach v'heichalach," then he has missed the essential meaning of what the bracha is all about.
Our brachos and tefilos are there to help us bridge the gap between the world of rugalach and the world of spirituality. In the midbar, when you live surrounded by miracles, you don't need that bridge. When you the life that we must live, b'derech ha'teva, you do.