Hey, @heytavo Did you get this resolved? If not, I believe this note in the documentation answers your question – Association type IDs:
“If a record has more than one associated company, only one can be the primary company. The other associations can either be unlabeled or have custom association labels.”
You are correct in needing to update or remove the existing Primary Company association before updating a new primary company for your record.
The docs don’t tell us why it’s not possible, just that there can only be one. I understand why this would be useful.