They sat at the counter as/since all the seats were filled.
I've seen both versions. For example here.
Are as and since are interchangeable in situations like these? If so, in which situations are they not?
Yes, they are interchangeable here. They are generally interchangeable when they have the sense of because. They are not interchangeable when they have other senses, especially their senses that relate to time. When used in relation to time, as means at the same time, and since means all the time after.