After talking to an Apple Care representative and trying a bunch of stuff over the phone which did not solve the problem, I have realised that one of my playlists contained a huge number of items. My Library contains about 10 thousand songs, but this playlist contains over 250 thousand songs somehow. I did not go through it, but it must have contained a lot of duplicates obviously. Anyway, I deleted that playlist and all the issues with iCloud/iTunes vanished. What I think happened was that every time I was doing a change that triggered iTunes to sync with iCloud the syncing a playlist with that many items would just take a whole lot of time.
I did create that playlist myself, but I never added that many songs to it and whenever I added songs I chose to skip duplicates. So I cannot explain how that playlist ended up being so huge.
A week or two later, after I had deleted the playlist and had no more problems with iTunes, the issues started once again. When I looked to the playlist section, the huge playlist that I had deleted earlier, was there again! That was really strange. I deleted it again and my problems are now gone for good. It has been almost a month since I have deleted the playlist a second time and it did not show up in my library again.
In the meantime iTunes has been upgraded to version 12.3 and I am using El Capitan as well. I hope these problems never come back.
Tip: although the guy from Apple Care was really helpful he was hearing about this issue for the first time. He had no idea there are complaints on the Apple Forums regarding such an issue. The point is to use the feedback form (http://www.apple.com/feedback/) to tell them about these issues to increase the chance of having them fixed sooner.