Firstly I'd go to easy urpmi
and follow the instructions carefully.
You'll be better off once you've got sources configured for Main, contrib, updates and plf. The first 3 are obvious in their uses. The last one, plf (penguin liberation front) produce extra stuff for mandrake (and possibly others, but mainly mandrake).
Once you've followed the instructions, go into "configure my computer" (aka the mandrake control centre), software manager>install go for yes when it ask's.
Once it's finished doing "it's thing", then look down the list of available packages and look for kdemoreartwork packages (if there's 2 with very similar names/numbers, I alway's go for the highest numbered one - which is probably the latest).
I've installed them all.
Then when you go into "configure my desktop" (aka the KDE control centre) you should have a choice of lot's of iconset's to choose from - recently I've been using "slick 1.5", but currently have gorilla icon's (try it, you'll see
Some of the artwork packages come with background's as well (plus wall papers).
It's very easy, because it has all been installed via mandrake rpm's (yes there are rpm's for other distro's, but if you try them, they might not work or you end up in "dependency hell").
There's also an absolute shitload of stuff if you have a look at KDE look
but unless it's specifically identified as a mandrake package, it may take a bit more effort to install.
Now your default icon location files are usually at
and if you follow my suggestion above for the kdemoreartwork then you'll end up with lot's of additional sub-directories for the extra iconset's you'd have installed.
As far as getting rid of the Mandrake star icon on the start button, I don't know yet, that's something I've been meaning to do as well, but if you have a look/login/register here
you should be able to find the instructions that I was reading earlier on how to accomplish that. The icon seems to be called Mandrake.png