Is it possible to build pay to script without destination address? I am thinking of a transaction that can only be spent if the recipient proves that he has burnt a specific amount of a colored coin.

Because the recipient is not known beforehand, is it possible that the recipient provides the destination address together with the proof when trying to spend the funds, or the destination address has to be always provided when building the scrpit?
Addresses are a human-convenience feature, and have little bearing on the underlying Bitcoin transaction.

Common types of addresses rely on sending coins to scripts that allow spending by signatures from certain private keys. However, you can have scripts that allow spending as long as any given locking requirement is met.

Unfortunately, the script must be self contained, and you will not be able to enforce a burn requirement, as there is no way to check if the coins have actually been burned on-chain. Your best bet would be to lock the coins to a key, and have an off chain way to share that key with someone who burns the required amount of coins.