If you intend to make a lot of decals, putting the effort into learning either inkscape or adobe illustrator will really pay off. Vector graphics really make this so simple.
it's not necessarily paint.net but the way he did it, you can obviously see he took his avatar's face and resized it. i tried making the same thing (because i'm making a bomb ass wario face pack) and it doesn't look all that pixelated
it doesn't look good because i just wanted to make it in like 3 minutes
image goes to download link