But when designing an "general" (if that even exists) engine, you cannot really know the amount of descriptors your user will need...
I think you can for the most part. If you have fixed level sizes (arena map, race track), you can pretty much know at load time what resources you have (number of objects, materials, textures, etc.), so you can size your descriptor heap appropriately. You can then add a a fixed maximum count to support room for dynamic objects that will be inserted/removed on the fly. Descriptors don't cost much memory, so it wouldn't be a big deal to over allocate some extra heap space. For more advanced scenarios, you can reuse heap space that you aren't using anymore.
For a level editor type application, I'd imagine you could grow heaps sort of the way vectors grow.
Another problem I have is: when you no longer require a given buffer, you no longer need its associated descriptor. So the best solution would be to reuse its location within the descriptor heap. But this requires me to implement some kind of advanced memory allocation algorithm, which I would like to avoid if possible...
I don't think it needs to be too advanced. Just keep track of "free" descriptors and whenever you need a new descriptor, pull the next free one. A lot of particle systems use a similar "recycling array" like this.
Imagine I have a set of drawable objects, each of them having their own world transform. I would use a constant buffer (one for each object) to pass the associated matrices to the vertex shader. Allocating them is easy, as I only need to use the location right after the last descriptor I allocated on the heap. But when I delete one of these objects, is it my responsibility to make sure that the space that is no longer used will be reused for the next descriptor?
I didn't really follow your question. The way I would assume you would do is allocate the cbuffer memory. Then you need to allocate CBVs that live in a heap that reference subsets of that cbuffer memory. If an object is deleted, it would be easiest to just flag that cbuffer memory region and CBV as free so it can be used the next time an object is created.