https://wiki.openstreetmap.org/wiki/Tag:shop=music
4503 uses (https://taginfo.openstreetmap.org/tags/shop=music)
I suggest using the same icon as amenity=nightclub but in shop-icon purple.
Makes sense for me.
It's better if we don't rely just on the color as a distinctive feature, so I prefer using different note shape (which should be easy - probably ♪). But since this is a record store, maybe there is something more resembling records (like half a disc visible from the sleeve)? We have some freedom here, which is good.
Some quick sketches of possible icons:

And my first attempt at an svg icon at 14x14: (.png copy)

Thanks, it's exactly what I've been thinking about to try.
From my experience: it's better to show only 14 px PNG versions (with links to SVG probably), because nice large scale design can make a better impression than it actually will look like on the map. I also number them to make it easier to discuss.
Thanks for the tips. Here's a few more ideas based on the record/disc theme:
2) 
3) 
4) 
5) 
6) 
7) 
8) 
I like 6 the most and I think the note could be probably thicker - the disc can take even just a half of space, if needed (as in 1-5), and would be still recognizable, I guess. Another quite clear picture is 7 for me.
Thicker note half disc:
9) 
Thicker note whole disc:
10) 
11) 
9 seems good enough for me, but please give the links to all of them just in case.
Could you make a PR and test rendering (probably using Docker would be easiest)?
I need to correct the colours in them first, there's some white where it should be transparent, and I also have no experience of using Docker, so it will be a while before I can make a PR and test. :)
They look great! 9) is okay.
But I would even prefer 11). The whole disc makes it somehow clearer to me.
@lakedistrictOSM Any news? Do you need some help?
@kocio-pl I've been busy recently so I haven't done much more on it yet, I'll give you a shout if I need any help :)
But I would even prefer 11). The whole disc makes it somehow clearer to me.
I would have to agree with that. The half-disc design doesn't look quite right.
@lakedistrictOSM Any progress there? I would love to see this icon included soon. It looks great!
Sorry for the delay, I'll try to sort it out next month. :)
@kocio-pl :( Unfortunately I can't proceed any further with this icon - I can't change the white areas to transparent. Probably the best way forward is for someone to redraw it - all parts pixel aligned, CD edges 1 pixel thick centered in middle of grid, music note (cropped from nightclub icon) is 2 pixels wide.

Or https://gist.github.com/lakedistrictOSM/ca42a78c33fe982544911e9283bd88b5
Hopefully someone with the right skills can take it from here. :)
OK, thanks for your design work!
Gist link with clean SVG: https://gist.github.com/Tomasz-W/09338c6cf9635ae63f7d5dda6fc3e9ba
Thanks!
So who wants to make a PR? @Jotam would you like to try?
Added the pull request, first time editing this, so go easy ;)
Resolved by #3123.