You could check it using a microflow: before saving or on change (of the reference selector) - retrieve the statuses with the same name and check their associations to type - if one that is currently selected already exists use the validation feedback activity or show an error message otherwise save.
Another way to do this would be to create an attribute of Type that is built up by an attribute of Status + an attribute of Type. This way you can specify uniqueness in even more detail, for example: if you have Project and File entities, you'd want a certain Project to have unique File version numbers, but other Files should be able to use the same version numbers. In that case: File.UniqueNumber = Project.Name + File.VersionNumber.