Synchronization in this case is expected to be done through the interlock operation itself. If your interlock doesn't respect primitive ordering, then you're not supposed to care about the primitive order, so no synchronization should be necessary. If your interlock does care about primitive ordering, then primitive ordering will be imposed by the interlock, so no other synchronization is necessary.
Primitive order defines that primitives generated by one draw call are ordered before all primitives from a later draw call. So if you're doing primitive order interlocking, then by definition critical sections from primitives in one rendering command will be ordered after those from a prior one.
So there's no need for barriers; what you want is primitive ordering.
Now, if you have one group of commands that only need critical sections and don't care about order, but a later group that themselves only need critical sections but need to come after the first, that is a contradiction. The second group does care about ordering, so they should use primitive ordering, not unordered.
Note that in order to make previous writes visible, you need the coherent qualifier. Ordering only guarantees ordering.