I could reproduce this issue by the steps you shared. For the bug fix patch, I basically agree to remove that assertion from build_replindex_scan_key() but I think it's better to update the assertion instead of removal and update the following comment:
IMO the assertion is using the wrong function because it should test a replica identity or primary key (GetRelationIdentityOrPK). RelationGetReplicaIndex returns InvalidOid even though the table has a primary key. GetRelationIdentityOrPK tries to obtain a replica identity and if it fails, it tries a primary key. That's exact what this assertion should use. We should also notice that FindReplTupleInLocalRel uses GetRelationIdentityOrPK and after a code path like RelationFindReplTupleByIndex -> build_replindex_scan_key it should also use the same function.
Since GetRelationIdentityOrPK is a fallback function that uses RelationGetReplicaIndex and RelationGetPrimaryKeyIndex, I propose that we move this static function to execReplication.c.
I attached a patch with the described solution. I also included a test that covers this scenario.