Mp3 & wma are not the same, they both are compressed formats, just different. So a portable mp3 will play just mp3's. If the player included a decoder for wma, then it would play it. Just dont expect it to.
The problem with what you want to do is that the quality of mp3's are not that great to begin with. So you will be re-encoding a second time. Since each format is lossy, which means data is lost during the compression stage, you will be doubling the amount of degrading audio.
I am not aware of any transcoders for wma -> mp3, so you will not benefit by the advancements of transcoding, unless someone else knows one for wma->mp3.
The only encoder you will want will be the lame mp3 encoder, it is a free encoder, based on the mpeg 1 layer 3 ISO. Other encoders can cost you money.
Some hardware decoders follow the ISO specifications very strictly, so you will want to make sure when you encode, if the songs do not play, then you may want to be sure to use padding for ISO compliance.
This is something lame can also do. Though not sure what hardware decoders are that picky.
I'd suggest you try using dBpowerAmp Converter, make sure you also download the appropriate codec's, available on the same site under codec central.
This program will convert your wma to mp3. This means it will take the mp3 file, decode it to wav and then re encode it to mp3.
Just another note, Mp3Pro is not the same as Mp3. Most portable players will not be able to handle this format.
Mp3 is "Mpeg 1 layer 3" and Mp3Pro is "Mpeg 2 layer 3"