I am actually inclined to say that high level PCs are very likely to become famous just by virtue of being very powerful, since that power can be so obvious that it will likely turn heads just as the PCs move around and go about regular things.
For example, let's look at the example of a group of PCs sitting in a bar when some random local tough comes up and starts a fight with them. One of the PCs decides to fight back.
Heroic Tier: The PC will probably beat up the local, but not without taking a scrape or two.
Paragon Tier: The PC will dispatch the local with ease, leaving no question that the PC is a man of great skill.
Epic Tier: The PC can flick the guy's forehead and practically knock him through a wall.
Heck, the sheer amount of wealth Paragon and Epic level PCs can carry around and spend freely will likely turn heads. Not to mention anything like Flying Carpets, Magnificent Mansions, stone figurines that turn into magical animals, etc.
So unless the PCs go out of their way to hide their power, it will probably turn heads at some point. And as soon as it has caught people's attention, the rumors will begin to spread.