Among the other properties as email, firstname etc. is it then possible to associate this contact to a given company by setting the associatedcompanyid property to the companyId I want to associate the contact with - In the same call of course?
This will work exactly as you expect. You can set the associatedcompanyid property when creating a contact to associate the contact with the company, by setting that property to the companyId of the appropriate company record.