Slightly harsh to just say pedal faster to a self confessed novice.
1st off the noise you hear in big cog/little cog is most likely going to be the alignment settings of the derailleur gears just needing tweaking slightly, as new cables bed in, and generally with riding, the mechanisms.go slightly out of adjustment and need a bit of TLC, easy to do - rather than me bore on through it here, use the search facility on this site, google is your friend as are Sheldon Brown and Park Tools websites for all things bike technical.
2nd, there are 2 schools of thought on pedalling: A) Grinding= slowly turning a big ratio between front and back gear set up using powerful leg muscles, B) spinning, fast pedalling on a closer ratio gear set up. In general people tend towards spinning a fast pedal stroke, but it is purely personal preference & element of what body type/geometry you are. You can gear your bike to suit whichever your mind and body are comfortable and happy doing. Listen to peoples advice and try it out sufficiently & if it works for you all well and good but if it doesn't then don't feel you have to carry on doing something just because someone told you it is right. Right for me may well not be right for you, all we can do is advise & suggest not definitively tell you how you ride your bike.
Back to the bike, MTBs tend to be geared more for bad surfaces on slopes etc and as such are geared in a more gentle manner with more teeth on the rear cogs and less on the front when compared to a road bike (giving an easier more naturally spinny ride and slower road speed in general) frame geometry, tyre size and grippyness (word?) all contribute too to making a MTB set up on the road a slower option.
The cassette suggestion by your bike shop is not wrong per-se, they will be no doubt suggesting that you go for one with smaller number of teeth per cog than you have now, this will make you go faster and likely see you using lower gears for the same speed as now / go faster than now in the top couple for the same leg speed. Kind of begs the question why they sold that bike in that set up to you, only to be seeking to change the gear combo (free? or are they gonna charge you for the cassette and fitting?) almost immediately after sale
*edit: Bear in mind that generally what you do to make the road element better will have a knock on effect taking away some off road effectiveness, tho with I guess a 3x9 combo and you being in 3x8,9 mostly now, you've got room to downgrade the MTB aspect and not lose it totally. End edit*
If you are intending this to be a principally used on the road bike then you may have made a mistake in buying/allowing yourself to be sold the current trendy option 29er; that you say is set up as off road 1st and foremost bike; over a different style that maybe would be more suitable to roads and some trail/off roady stuff , such as a hybrid, cyclocross or for more exclusive road use : flat or drop bar road bike. You can kit the Cube out for better road performance than you have now, change the cassette, smooth tyres, maybe a more leaned forward aggressive headset to get you lower and more aerodynamic?? but you may well end up getting rid for a more specific road style bike as you get more into riding and if you find the road is your happy place.
If you are just riding it on the roads to get you to MTB heaven & somewhere with slopes and rocks and jumps etc that you'll be doing most of, then the compromise of a soft road ride for more effectiveness where the bike comes into its own is one you'll have to live with and pedal harder to go faster ;-)