Insert multiple sObjects in single DML call

You need to use a related field Contact__r to associate the Contact to AccountContact__c.

Try below code,

List<sObject> records = new List<sObject>();
records.add(new Account(AccountExternalId__c='1234555', Name='ABCD Company'));

records.add(new Contact(account=new Account(AccountExternalId__c='1234555'),lastname = 'Testlast', ContactExternalId__c='3525'));

records.add(new AccountContact__c (Contact__r = new Contact(ContactExternalId__c='3525')));

insert records;

You need to use the name pointing reference. Here, that would be Contact__r.

It might be more clear if you look at how it works if you set the value dynamically: you can either call set with the Id, or setSObject with the record.

AccountContact__c junction = new AccountContact__c();
junction.set('Contact__c', someContactId);
//OR
junction.setSObject('Contact__r', someContactRecord);

Also, note that you can always get the name of this relationship through the describe.

DescribeFieldResult describe = AccountContact__c.Contact__c.getDescribe();
system.debug(describe.getRelationshipName());

In your working case, the field has an API Name of AccountId, and a Relationship Name of Account. What you're trying to do in the junction object is analogous to if you modified your working snippet as follows:

Contact record = new Contact(AccountId=new Account(...));