If the SIDs for ##certificate-based## SQL Server Logins don't match across replicas in an Availability Group, will this be a problem on failover?
Is this of concern? Will a fail-over work despite these Logins having mismatching SIDs between some replicas?  


I don't think this is a concern with fail-over due to following facts:


The fail-over basically targets user databases based on database mirroring endpoint 
CONNECT permissions on the ENDPOINT required to user defined LOGIN or SERVICE ACCOUNT (not for server principals named like ##%).  


As you mentioned, fundamentally, the SID is the correlation between Login and User in a database level. Since the server level metadata sync is out of scope in availability groups, we must maintain Server Level login's SID same in all the replicas (SQL Instances), so that it would match with User SID in secondary copy of the database.  

When fail-over happens there is no failure of application connectivity as the login SID = user SID, eventually application gets the same permissions on the database. Otherwise users in database become Orphaned 

Following are some points that indicates why we do not have to concern on server principals that are named '##%':  


These are created during SQL Server installation, we do not have control over these to manage SID  
These are only internal purpose, meaning only exists in system databases, doesn't have any relation with user database principals (sys.database_principals)  
There is no issue with user DB connection, since any application usually doesn't have any relation with the principals that are named like '##%', and the principals (##%) not existed in user database.   
Finally, our aim is to match Server principal's SID = database principal's SID within each replica. For the principals that are named like ##% are by default and always maintains same SID within replica which you can verify with following query: 


select name, sid from sys.server_principals where name like '##%'

select name, sid from master.sys.database_principals where name like '##%'
select name, sid from msdb.sys.database_principals where name like '##%'





  As I understand it, server-level objects must be kept in sync (aside: then why isn't it part of AG by default?).  


You're right, it's limitation of availability group which clearly stated here.., in this case contained database feature would be a solution to persists the authentication with database itself. 

Not only logins, but also there are server level metadata aspects that need to be manged outside the availability group as required.