The company name cannot be created or updated in that part of the request body JSON.
"company": {
"company_name": "string",
"id": 0
}
The name here is read-only; it is simply included for your convenience.
But, good news: the REST API will soon have a resource for Companies, separate from Contacts. In the meantime, you can create Companies through the XML-RPC API.