TLDR: This criteria had to do with post-USSR Eastward enlargement criteria and shows up in a NATO summit of January 1994.
This was what I originally thought, and put as a comment:
I wonder if it wasn't a blurb added at the time to explicitly filter out Communist countries, keeping in mind NATO's original reason for being was to oppose Communism in the European theatre. No more, no less. However, if that is the case, how would that be proven? You need an "X was added at the request of Y to achieve Z". You sometimes see widely publicized attributions of small edits in treaties to some party for some reason, but that is not always the case, even if minutes of meetings still exist somewhere.
I was wrong. When I wrote this, I thought it was something that was old in NATO's DNA, from the beginning. But it seems to be more recent than that, 1993-1994 timeline.
It surfaced during the January 1994 NATO summit. As per "Security and Defence and enlargement of the European Union (2)", from the EU Parliament:
In December 1994 the North Atlantic Council announced that it was studying the enlargement of NATO. Several principles were proposed.
The aim is still defence of the Alliance's vital interests and promoting stability throughout Europe.
Reasonable and gradual enlargement of NATO should be open and not secret.
There is no timetable or list of countries invited to join. Questions 'who?' and 'when?' will not be answered until the end of the first half of 1995.
Each country will be considered individually and not as part of a group.
The Alliance alone will decide which countries can join and when. No non-member country will have the right of veto.
Even though membership criteria have not yet been defined, future members must be democratic countries with a market economy, committed to security policies, and responsible and capable of contributing to the Alliance.
Each new accession to NATO will entail a solemn commitment for the United States: a defence treaty that holds out the American umbrella for the country concerned.
Furthermore an article dated May 1995 says indicates the criteria had been a recent development (and thus likely triggered by the collapse of the Warsaw Pact). And it also indicated that NATO thought it could afford to be picky:
During the Cold War criteria did not play a major role when NATO expanded. When the Federal Republic of Germany joined NATO in the mid-1950s it so under clearly different circumstances than did Spain in the early 1980s. Both cases, however, served the Alliance's strategic interests.
...
which criteria should be applied has been debated for more than a year. Among them are:
Commitment to democracy and market economy.
At a guess? NATO explicitly did not want to take on take on East European countries that hadn't "reformed" to its liking. Not so much Russia, as places like Bulgaria or Rumania for example (both countries that took a while to shake off old habits).
It wasn't meant to keep Communist countries out, there were not many left in Europe by that point.
But it might have been meant as a carrot: you can join us if you are like us. Part of it might have been to pressure countries into capitalist reforms which could prove profitable to existing NATO members. Part of it might have been to steer free of train wrecks - post-Soviet Eastern Europe went through some pretty drastic economic contractions after 1991.
But if you want to know more you probably need to expend more Google-fu around the run-up to this January 1994 NATO summit and the horse trading around enlargement at that time.