I don't have a dev environment in front of me at the moment, but something along these lines should work:
- Set truncateToFit property of the Label to false (OR use a TextField with wordWrap set to true - I think this should keep the words together as much as possible).
I haven't had the need to use any of the above yet, and hopefully you haven't tried them yet because it would be an easy solution to a part of your problem. Without any code, I'm not sure why padding didn't work, but maybe it's something to do with the word truncation.
As an alternative, why not use a Button, embed or specify a source for your icon and decide where to place the text by specifying the object's labelPlacement property?
EDIT: Since there's no property in Button about wordWrap, as they would recommend in the Adobe Flex forums for such questions regarding sizing based on content where there is no automatic feature to do that, you have to find the longest word and adjust the width of the button (i.e.: in the creationComplete event). Experimenting to find the font to pixel ratio would be my best bet (or you can use a Monospace font where all the characters are given the same space thereby simplifying the estimation):
creationComplete="event.target.width=returnMyWidth();"
As for the padding, it may be related to the custom width that you had set or it may be from embedding the image automatically setting a padding by being included - I'm not really sure, so it would be good if someone can offer a comment based on experience with this.