Would converting them to a lossless format like FLAC or APE (both of which my PMP can handle) limit the damage of transcoding?
Would that be a Cowon device by any chance? Try renaming the files to *.mp4 and see what happens. Some Cowon players have unofficial support for aac.
If not, you'll need to transcode them. Why don't you simply get the ABX comparator plugin for foobar2k and do some blind tests? Convert the files to flac and to various bitrates of vorbis and mp3 and do a blind test.
This is the best method to make sure you're satisfied with the sound quality of the conversion. Nobody here will be able to tell you what conversion settings are the best since it all depends on what you can hear.
Or, if you decide to convert to a lossy format (like MP3) using a higher MP3 bitrate should help, and you probably won't notice any difference in sound. (The only downside to higher bitrates is bigger files, but the files will still be smaller than the lossless formats.)
Interesting you say "it all depends on what you can hear"; I said something similar as part of a question in my very first post here, and got an official warning - something I'm still a bit grumpy and shell-shocked about, to be honest...
I figured this might be the case. I tried converting the files to FLAC via foobar2000 before I posted, but the files swelled from about 80MB to nearly 500, which was a little alarming! ;-)
people make all kinds of silly claims, like speaker cables, and even power cables, making a difference in sound quality.