Yeah, scan jobs that loop over all the players will get quite slow and/or resource-hungry when there's lots of players, so although it can work ok with a small player base, it may not be the ideal long term solution for this.
If the operation has predictable timing (i.e. you can calculate when the player's next notification should happen), this could be a device-local notification instead.
If it's not predictable, but rather need to try the operation and check the outcome to know if the notification needs to be sent, that might need some kind of custom server-side mechanism.
Like an entity to which you could register these per-player scheduled operations and that entity would handle the timers and wake up the player entities at right times. That could possibly be made into a generic SDK feature but at the moment it does not exist. At big scale, the implementation would probably need some sharding to avoid dealing with huge player lists in a single entity.
Or, your idea about the time-for-next-check DB field sounds like a viable approach as well. It could be a separate database table (separate from the main Players table) with an index with the time-to-check column, to ensure fast queries.
Regardless of the actual mechanism, proactively doing server-side operations for all players can be troublesome as it can cause spikes if the operation happens at roughly the same time for all (or very many) players. If the operation is known to happen at different times for different players, and therefore spread out smoothly over time, it should be okay.