It's possible an add-on or web page is intercepting that keyboard combination, or that your Firefox installation has become damaged. Hard to say without more information.

The "Clear Recent History" feature also should be available from the History menu, either:

• "3-bar" menu button > History > Clear Recent History
• (menu bar - tap Alt to activate) History > Clear Recent History

Is it still listed there, or hidden/grayed out?

Make sure you do not run Firefox in permanent Private Browsing mode (Always use Private Browsing mode; Never Remember History).

• https://support.mozilla.org/kb/Private+Browsing

• Options/Preferences -> Privacy -> Firefox will: "Use custom settings for history"
• Deselect: [ ] "Always use Private Browsing mode"