shared, wrote in my original post. :)
After many tries, I succeeded to have it working from other users by actually changing the order of the Set Item Permissions boxes.
First the user, then all the others.
But now I have another issue, maybe you can help -
The whole workflow takes about 3-4 minutes to complete, while the first permissions grant takes a little less than a minute. At that time-frame, anyone in the company can access items created in the list until the permissions are granted successfully. How can I avoid this from happening or how can I have the workflow work faster?