SOLUTION (for me):
It happened because I was logged in on Youtube and tried to add the Video to my Playlist. It probably could not get the Video because of some Verification Error (the video you watched and tried to connect is connected to your account). Or a other problem could be because of some youtube block against Brave Playlist.
To resolve this Problem log out! You might not find that option so fast. I reccomend holding your Phone horizontal and “request a Desktop site”. (Then it looks like on the Laptop/PC). To request that go to Youtube.com > three dots on the top or bottom (depends on the layout) > **request dektop site**
I tried to download the songs again in Mobile mode. It didnt work. I guess I will stay in Desktop Mode to download/play Songs in Playlist. If someone has a propper solution please 