If you want a KDE desktop then I recommend Kubuntu. I have tried them
all and find Kubuntu the easiest to use. It has all of the advantages
of Ubuntu without the problems associated with Unity. I have not used
Mint KDE, but question their dedication to KDE when they have so few
developers and are already split with Cinnamon and Mate. Mint KDE
seems to be an afterthought which shows lack of direction to me.
Kubuntu is dedicated to only KDE and has been around since the
beginning and is now independent of Canonical. Win. Win. Win.

Others to consider would be openSuSE and Fedora with KDE, but that
involves learning a new package management system.

As for a new laptop, there are many that work well with Linux. The
only manufacturer that I would steer clear of for lack of Linux
compatibility is Toshiba. It might be worthwhile taking a live disk
with you to the store and re-booting their machine with the disk in.