Here is a quick example sketch: This is supposed to be a big, strong, evil, imposing demon-sculpture, but to me it just looks a bit too cute and cuddly. What should I be doing to make it look more scary?
I think you are on the right track already with your character. You just need more definition in order to relay the emotion or personality.
See the brown marks I added.
Simply adding facial definition & detail will help bring out the "evil" in the character. Note how the eyebrows protrude a bit more now. More wrinkles at the bridge of the nose makes him 'snarl'. Depth lines around the cheek bones define the face and give some age.
Also, add more detail in the body (i.e. muscle tone) to keep the character from looking "soft".
It's very helpful to have a small mirror handy when drawing so you can mimic facial expressions and positions to find key points draw.
Consider reducing the size of the head. It is out of proportion to the body.
If you look at most cute and cuddly cartoon characters, their features are exaggerated to make them look more cute. Most cute characters have overly large heads and eyes…mimicking a baby's appearance.
In this case, your characters does not look cute, however the fact that your character's head is so large may be aligning with big-headed cartoon characters (and babies).
I suspect if you reduce the size of the head a bit, say 80%, you'll get a more fierce looking character.
See here for head sizes and proportions: http://en.m.wikipedia.org/wiki/Body_proportions
You want to be more towards the adult side of the scale and less towards to baby side.
I also think your character's arms could be a bit longer, they too are a bit out of proportion. One of my favorite drawing books is a book on human anatomy - maybe check out some good anatomy books online/at the library, it will help. Or just Google drawing the human body, etc.
For example (simple scaling reduction of the upper head, and then further reduction of the eyes in GIMP):