Unfortunately there is no way to trigger WP deprecation warning for PHP constants.
What I can suggest – to use your constants and “theme support” options together. First for backward compatibility, second for customization facilities. Your theme will have to rely on “theme support” options only, and keep constants only for child theme.
The trick is in the way of declaration such constants. You have to define your PHP constants based on what has been added to support by theme.
After updating your theme, you need to let people know that you don’t use PHP constants any more and you will remove PHP constants in further releases. You can place such information on a site via which you distribute your theme.