Just create a menu for "playlists"
the users will be able to "add songs to playlist" using the button next to each song (+)

then on the playlists menu they can choose to store permanently the playlist to the system.

I did so but the useres only can choose 'add to current playlist' but they can't create one.

What did I miss ?

the option to "create" the playlist (which is actally "store") is visible on the PLAYLISTS menu, next to the "on the go" playlist they can choose to permanently store it.

they NEED to be registered users to see the option.

Hi,
My users are registered via Comunnity Builder but there is still no chance to add playlists.

The playlist menue item looks like shown at the attachment.

Could you please give me some advice ?

the button is right there on your screenshot... on the right there's the little "disk" icon, which is for SAVING the playlist.

first you need to add some songs to the playlist using the (+) button next to each song.