Hello, I'd like to give my comments.
Firstly, you said that you're using paint. I think it's not a good program to really draw, I mean sketching with it is okay but coloring with it is actually a no-no. I suggest you try GIMP, it looks like photoshop but it's freeware.
The first character, Callidus, I kind of agree to one of the comments above that he looks a bit too villain-ish. If you really want to make Callidus cute, I suggest you making his costume cuter, like loose jacket or T-shirt or something. Trust me, it will look cuter, even if it's still dark-colored.

Oh, and I think you may want to redo the lines of his hair. I like the first one's hair. Did you use a big-sized brush on the second design? Because hair usually looks better with small-sized brush.
For Lucian... I don't know, I think he's a bit too girly. Cute, yes, if you'd redo his body (it doesn't look proportioned). And maybe his face is a bit too girly...
Well, hope that can be a help. Sorry If I seem too harsh, I didn't mean it that way, really m(_ _)m