Most if not all programs nowadays have a "stack" for objects with a size known at compile time, and a "heap" for dynamically allocated objects.
Where is this implemented in practice? Is at the CPU, OS, or program level? Does every program have to ship with some code to handle stack and heap management?
Could a new programming language come along that uses a completely different memory paradigm and still run on current OSs?
What you are thinking about is basically covered by the platform ABI (application binary interface) which includes details like calling conventions.
There are plenty of programming languages that do not use the system stack or only use the system stack for interop purposes. It is much more common to use a different stack in interpreted languages.but several compiled languages implement their own stacks. Usually you want to implement your own stack if you want easy closures or advanced control flow features or green threads like in Go.
Many garbage collected programming languages carve out their own heaps. There is a minor issue with not being able to use shared resources like sbrk but that is usually not a problem as alternative APIs like mmap are usually good enough for acquiring large blocks of memory. Ostensibly for ASLR (address space layout randomization) mmap is better than sbrk.
More directly there is resource constrained software that does not use a heap or stack but simply allocates all memory statically. Usually you carve out memory into buckets you dynamically allocate from anyhow. This sort of thing is less common now.
From a formal methods perspective the heap and stack correspond to the "Store" and "Kontinuation" of a CESK machine (Control Environment Store Kontinuation.) There's also a story about one hole contexts and stacks but I'm less clear on that.
