Is a Decentralised Exchange possible on Cardano-CL?

Yes. There’s nothing known for now that would stop you from doing this.

You can also read this whole topic and think of a decentralised exchange as the same kind of functionality but just a lot more complex: