I don't have any need for security programs or encryption. I wouldn't use LMDE. Maybe they have improved it since I tried it last, but it required a bit more knowledge. Linux Mint Julia is probably a better bet. I think it supports encryption.
The KDE version is fine as long as you have a good computer system but like Windows 7, it has a few overheads. I don't like it much but I use a few of the KDE apps on Cinnamon. KSnapshot is handy for making screen shots and there is a good FTP app on KDE too, but I use File Zilla because I'm used to it. This video shows how to customise KDE. You might like it. A lot of people do.
I would stick with the Cinnamon distribution which also comes with the option of Mate. These are desktop environments. You can try out either Mate or Cinnamon. It's packaged together. You'll like the installation. Just burn the ISO to a DVD and boot off it. If you're connected to the net with the computer, you don't have to choose your local time or anything. It detects it for you.
Cinnamon needs a few tweaks if, like me, you use a HD monitor. There is plenty of information online. I've never tried Windows on HD, but from what I see, it needs some customisation for that too.
No need for restarts. I think more people will probably try it, since they are used to different operating systems these days with Android phones etc.
Try some of the other distros if you want to experiment. XFCE is not a bad desktop these days.
Ubuntu these days reminds me of Windows 8.
You could even install Android. I've never tried it on a PC.
A tip - try looking for test runs of various Linux distros on You tube. If you install Linux Mint, you don't need to keep everything as default. I use gnome icons as standard and a personalised picture on the desktop.