This is super reminiscent of the shoehorned-in "Starglider" subplot in Clarke's Fountains of Paradise. Starglider shows up, asks a bunch of questions, claims that only species that form family units come up with the idea of religion, etc.
More about that from here:
Clarke complicates his story somewhat with the unexpected arrival of
an alien probe named Starglider, which arrives, Rama-like,
communicating openly and changing the world forever before drifting
on. The idea of unseen aliens giving us a bit of a nudge in our
evolutionary path is a theme Clarke famously explored in 2001 and
Rendezvous with Rama, and it worked much better in those stories.
Here, Starglider seems a bit tacked on (as if the concept of the
Orbital Tower isn't SFnal enough), and Clarke introduces the wholly
improbable idea that, simply by virtue of Starglider's testimony that
the existence of God is highly unlikely and unnecessary (and found
only in a small handful of the hundreds of advanced alien cultures it
has discovered), all religion on Earth basically stops. Although this
might be the atheist's and skeptic's dream scenario, it would simply
never happen that way, because the entire psychological drive behind
religious belief is the desire to hold that belief, and a religious
fundamentalist will hold onto his belief system even if
incontrovertible proof it's all wrong is presented. Faith is an
emotional process, not a rational one, and the scenario just doesn't
ring true. What would really happen is that religious fundamentalists
would vilify Starglider as an emissary of the devil, sent to lure us
to our spiritual doom; conversely, religious liberals would simply
shrug the whole thing off and pronounce that God has simply made other
provisions for the salvation of these aliens, and/or will reveal
Himself to them when He sees fit. Starglider's pronouncements, if
anything, would lead to a renaissance of religious fervor. That alone
could make a novel in itself.
But, it's not a short story, and Starglider doesn't orbit Earth, it just flies through the solar system.
None of it has anything at all to do with the main space elevator part of the novel, so maybe that's why you remember it as a short story.