What can we do with this recipe to make it less bitter? I like Yakisoba, so I want to try to make it work rather than having something different. But I'm afraid that if I add something (like sugar) it would change the recipe's flavor too much.
I'm at a bit of a loss providing advice on this issue because I've never heard of it (short of burning the ingredients in the dish). There's a very, very slight bitterness in proper ramen-style noodles because of the alkali content of kansui (potassium carbonate and sodium carbonate or bicarbonate in water solution), but in typical noodles of reasonable quality I would expect the bitterness to be lower than, say, the outer skin of a pretzel.
To me it sounds like you've stumbled on poor quality noodles, or you're hypersensitive to the very mild alkali content. You might consider looking for Chinese egg noodles instead, which have a similar color but may have less or no kansui, or you might try a completely different noodle, such as udon, and make yaki-udon instead. Alternatively, consider trying a different brand of noodles, or a different form (dry instead of refrigerated, frozen instead of dry, etc.) One local brand of refrigerated noodles meant for yakisoba available where I live (Seattle) has been so inconsistent in quality for me that I skip it and go straight to the (probably imported) frozen ones in our market. (Dry ones will require brief boiling), but in my case our complaint was about texture, not bitterness. Switching out for a different supplier may resolve your issue.
ETA: It occurs to me that if you were starting from dry noodles, you may encounter rancidity with unusually old ones. That's a bit more aggressive than just bitterness, but I've seen it on occasion with long-forgotten packaged noodles; it was obvious before cooking, though, so I've just tossed them.