Welcome to Salesforce Stack Exchange!
I'd say it really depends on what you mean by "Users". If you're setting up something like a managed package, where "Users" are admins who can select any object (entity) in their org, that's one problem. If on the other hand you're the admin/developer for a single Salesforce org, and "Users" here means users of your org, then that's a different problem.
In both situations, someone at some point is going to have to do some sort of "setup" to tell Salesforce to listen for changes to a particular object. Salesforce won't do this automatically, for efficiency purposes; it has to be somehow told to listen for changes. With that said, you do have options (depending on how hard you want to work) to minimize the necessary setup. I'll assume from this point forward that you want non-admin users to be able to set up notifications in a single salesforce org.
As you mentioned, change data capture is a great option, except that you need additional licensing to have more than (10?) objects. (Last I checked, the limit was 5; I'll be excited to learn if that's been upped to 10!) Also, it has to be turned on by an admin user. If you want non-admin users in your org to be able to turn it on, then you have to do some fancy footwork with the metadata API. Here's the basic run-down of how that might work, assuming you bought the license for enough change events:
- Create a (normal) platform event, Change_Subscription__e. This has a field for the id of the user subscribing, a field for the API name of the object, and a boolean field to represent the subscription as on/off.
- Create a custom metadata type to represent a change subscription, Change_Subscription__mdt, with fields similar to the platform event.
- Create a generic lightning component that can be used on any record page. It gets the current object type, and the current user, and searches for a Change_Subscription__mdt record that defines whether or not changes are subscribed for that user/object combination. If none exists, it assumes not.
- The lightning component contains a control to toggle the subscription state from off to on, or back again. This publishes a Change_Subscription__e event.
- Create a trigger handler for the Change_Subscription__e event. This does three things. First, it checks (via the metadata API) to see if the provided object is currently configured for change data capture. If not, and the subscription is being turned on, then it turns on change data capture. See the metadata type PlatformEventChannelMember.
- Second, whenever change data capture is turned on, the trigger handler also creates via the metadata API a new change handler for that object. This change handler performs whatever logic you define (e.g. posting to chatter) to happen on record changes.
- Third, the trigger handler creates/updates the Change_Subscription__mdt record that corresponds to the object/user combination.
- Create a PlatformEventSubscriberConfig metadata record that changes the running user of the platform event from Automated Process to an admin user. The purpose of the platform event is to allow you to "change users" from a normal, non-admin to an administrator. This will allow you to make changes to metadata through the metadata API.
- While waiting for the Change_Subscription__e event to be processed, the lightning component should poll the metadata record, until the status is successfully changed.
If you don't want to use change data capture, a similar methodology might be used with object handlers and normal platform events:
- Create another normal platform event, Change_Notification__e. This can contain fields relevant to published changes, such as the field that was changed, old and new values etc.
- In the Change_Subscription__e trigger handler, when a new object is encountered, instead of turning on change data capture and installing an event trigger handler, you can install a normal object trigger handler that publishes Change_Notification__e events whenever fields are changed.
- For efficiency purposes, it's probably worth limiting the fields that are checked for changes (otherwise, for large objects with hundreds of fields, you'll have to check all of them for changes on every update. This can be accomplished by creating another metadata record type called Change_Subscription_Object_Settings__mdt, and giving it a long text area to hold every field requested for tracking by the lightning component. Then, the trigger handler for that object queries this metadata, determines which fields to check, and publishes events only for those field updates.
- Write a single trigger handler for Change_Notification__e that performs the notification logic. Note: all notifications for all objects will go through a single platform event, versus the different platform events in the change data capture strategy. This is an additional reason why you should only perform notifications on select fields, rather than all changes. Otherwise, the platform event can get backlogged, depending on your org's traffic/update frequency/number of users using this feature.
Hope that helps. Here are some resources related to these options: