Thanks for all the help and advices. I went through with it on Friday night. Pretty straight forward as expected:
1.) Back'ed-up all the game saves on USB-stick from all users
2.) Downloaded latest firmware to the USB-stick
3.) Swapped harddrive
4.) Started PS4, installed firmware, started downloading all purchased games and copied game-saves from USB-stick back to system storage.
Worked flawless.
A few things that are highly annoying though and IMO rather weird too:
1.) Game-saves can only be copied back to system storage if the game is installed on the PS4
Annoying since I didn't want to download each and every game I don't play anymore (or don't intend to for a while at least), but because there was no other way of copying over my game-saves, I still had to download those which was an extra 40 GB of data. And with PSN being quite slow and varying between 2Mbps to 20Mbps on average, not something I was keen to do. IMO a bit of idiocity of Sony to limit this for god knows what reason.
2.) It was rather difficult to find all games I had purchased off the PSN store. It would be great to have a option where all purchased games are listed. If there is, I couldn't find it.
3.) Game-saves of local users without a PSN account tied to it can not be back'ed-up and restored.
Hugely annoying. I had created a local user for some games because I either wanted to try out a few things with the games without altering my main play through - or in another instance, started playing a playthrough (The Last of Us) a 2nd time with someone and did this using a local user. It would be daft to link them to a PSN account since they are only to be used locally, but that the system prohibits me from actually backing up these saves are rather annoying. No idea why there would be such a limitation in the first place. It's a simple save. Probably because game-saves are linked to PSN user IDs or something. It's still stupid and annoying. Lost a TLoU game-save with ~20 hours of play time on it because of it.
Anyway, despite these 3 annoying points - about 40 hours later, most games are back installed and I still have about 350GB of free space. Yay!