This is totally possible! I don't have my Zen handy, so I can't give you the exact buttons to push, but in the "synch" or "send to handheld" dialog box, click the options button and there should be an option to convert format during transfer. I would recommend transferring your WMA files in a separate batch than your MP3 files so that only the WMA files get converted and the MP3 files are left alone.
Point 2: SMARTLISTS! It sounds like you created a playlist containing thousands of tracks. Smartlists are a much "smarter" way of doing that kind of thing. For example, my "files for Zen" smartlist has the rule:
[media type]="audio"
That means that I send all audio tracks to my Zen. If I wanted to be more selective, I could do something like:
[medai type]="audio" -[album]="album1","album2"
Which would send all audio except album1 and album2. For the ultimate in flexibility, put a string in one of your custom tags (like Custom 1) and use that string as a flag that the file should go to your iPod. For example, take all the files you want to go to your iPod and set Custom 1 = "iPod". Then make a smartlist with rules:
[media type]="audio" [custom 1]="iPod"
Now you can easily add and remove files from your iPod playlist by editing that tag. I find that much easier than manually updating the contents of a playlist.