Is it possible to convert a plain text field to a rich text field, without losing content?
You should be OK converting your Plain Text to Rich Text. I've just tried it in my dev environment and everything was preserved.

Rich Text will add the paragraph tags as you suggest, so you'll want to remove them from your templates files as you mentioned.

If you're being cautious, you can take a backup of your database in the Settings section of your control panel before changing the field type. It only takes a few seconds, and that way, if anything goes wrong, you can restore.