Lots of times people don't realize that there are two type of Pasting in paint. There is one where the full rectangle of the image you are trying to paste is non-transparent. but there is one other method, a second selection, that will allow the white area around a graphic to be transparent.

It sounds like you are using the default, full rectangle, selection. try the other.