In the mameluke empire there are scholarly records of philosophers and educators lamenting that stringed instrument players and singers are more critically acclaimed than great physicians and mathemeticians. These early pop-stars seemed to derive thier fame much the same way our "famous for being famous" types do today. Mass exposure and marketing and associating with the rich and powerful. They just used different methods to do so. They travled a lot and hired criers to announce thier arrivals, which were usually accompanied by extravagant displays of wealth and spectacle. Think alladdins initial appearance to jasmine while masquerading as a prince. Everywhere you go you hire troupes of dancers, animal handlers to parade rare and exotic beasts, slaves or servants to sing praises toss out handfuls of coins or loaves of bread and generally add to the jovial atmosphere, fire-breathers, jugglers, bare chested women etc etc. If nobody knew who you were before they do now, and if you have the musical or choreographic talent you then make a big deal out of presenting yourself and your services to the local strong-man. After such a blatant display of wealth and pomp he basically has no choice but to respond in kind, a big festival is held, lots of wine is drank, lots of babies get made, lots of coin flies around. His people get distracted from thier crushing poverty for a while, thier leader reaffirms his power and benevolence, and you get a bit more famous. He presents you with lavish gifts and you depart. Rinse and repeat.
Thats not to say it's foolproof. History is rife with tales of famous entertainers whose careers met nasty ends because they caught the local despot at a bad time or somehow offended him, or perhaps served one of his adversaries and ended up on his bad side. Or maybe he became jelous and wanted you all to himself. Or maybe just couldnt afford to pay you so decided to accuse you of something and have you punished. Or maybe hes just a bit inbred and a lot mad and just likes seeing guitar players tossed off of buildings.
Its a lot more dangerous than modern day celebrity-hood, but before electronic recordings and telecommunications there were indeed singers and dancers famed across entire empires. They just had to travel a lot and have enough money and connections to promote themselves a lot. Basically you use your talent to get noticed by a wealthy patron, hopefully getting onto his permanant court of sycophants. He will use you to show off to other visiting dignitaries. After a few years he dies, grows bored, or just lets you go. You now use those connections to travel and patronize the courts of the high and mighty. Eventually you become wealthy and wideley recognized enough that you can become your own promoter and travel as you wish.