1. It is possible that you are not translating the right string for your widget title:
- Go to WPML > String Translation
- Click on the blue link at the bottom of the page: "Translate texts in admin screens »"
- Look for an option similar to "widgets".
- Check the checkbox for your strings of interest.
- Click on the button "Apply"
Now, all your selected strings, should appear in the String Translation panel
2. If this still does not work you can consider to use our WPML Multilingual Widgets and create a different widget for each language.