How quickly would word spread of an upcoming musician in the Forgotten Realms (5e)? It wouldn't be a direct comparison to the medieval times of our own world as they have several ways of communicating across long distances.
Depends on the individual location. In general, cities would come to know first, because they have more sophisticated communication infrastructure (more Wizards) and more people travelling there to potentially spread rumors. However, it is unlikely that word would spread quickly unless there was a promotion for the Bard's next performance. So, if your Bard is touring to Neverwinter after Waterdeep, Neverwinter would be abuzz with talk about "the up-and-coming rock star from Waterdeep," but it's unlikely that another city like Luskan or Silverymoon would know, because no one is promoting him there.
If you think that promoting a rock star is only a modern invention, think again; as a landlord or venue owner, there is no point in hosting a musician if you don't promote him so you make more money from the performance. Likewise, if he's not performing anywhere in the city, then nobody would be compelled to promote him. This is kind of a crucial phase in his career because he needs to invest a lot of money initially to get promoted, and this is where the bulk of the cost he needs to pay for his fame would come in. Once he's famous in a region, his name as a Bard will have inherent value due to his popularity and venue owners will want him to perform at their locations, but until then he has to foot the bill for promotion.
Rumors of his performances will spread regardless of promotion later on, but you have to allow time for people to travel and spread those rumors. An unknown musician lives and dies by any promotions he can get from touring, since he can't generate buzz by himself. After he performs in a city, he'd make a lasting impression there -- see also the "Entertainer" background feature "By Popular Demand" (assuming your Bard took this background).
As far as villages and hamlets go, as long as they're near a city where they can actually go and see the Bard perform in a reasonable timeframe, they might well take a liking to him. But settlers of fringe and frontier villages and outposts, such as Noanar's Hold on the edge of the High Forest, probably won't care, even if they do come to know about him. Life in these areas is extremely hard (remember, they have to deal with Orcs, Centaurs, occasionally hostile Elves, etc) and most people don't have the time or means to go see a performance like this. Many of them are dedicated to their hard lives (Rangers, Druids, etc) as well.
So, my question is: how would I track how popular he is? I could easily say "oh you are popular here because you played here", but he wants a more realistic way (which I am all for) to track his fame, and since looking at his name on th iTunes chart isn't a thing that can happen, I've turned to asking you all.
I suggest that you track your Bard's "regional fame" as a broad abstraction. The easiest way to do it while keeping it accurate is probably to do it on a regional basis. For instance, if your Bard plays in Waterdeep and Baldur's Gate, word will probably begin to spread to Amn and other nearby areas along the Sword Coast. Consult a map of Faerun after he performs to gauge what settlements his fame would spread to. In the end, it doesn't matter, as long as it's easy for you. Keep in mind where he's being promoted next, too, when he's unknown in a region. You can use this to see if people know about your Bard before he enters a city; you can either roll a check using the Bard's proficiency, or roll a check for the NPCs to know about him. You could even make the DC easier if he's done more gigs in the region. Think of it as kind of a "plus" version of the Entertainer feature, which only takes effect after you've performed somewhere.
He was thinking about enchanting objects to play his recorded music but I didn't know if Forgotten Realms (or any DnD world) has the capabilities to make a "CD album".
Although RAW spell effects might make this somewhat difficult, this is easily within the power of your average hedge Wizard in the Forgotten Realms in terms of lore or fluff. Consult the DMG for help on making a suitable magic item. A three-to-five minute long audio recording with a permanency effect might be a bit pricey, but it's hardly the magical equivalent of rocket science -- if the RAW spell levels are any precedent. Would definitely be a hit amongst the nobility.