What is the best way to restrict the scope of a connected app to a set of objects? My current solution is to use the Manage user data via APIs
scope but that still grants more access than required.
A solution I see frequently is to create a user with a restricted profile and connect with that user but then you lose context of actions made by users in the connected app so this solution doesn't work
Tricky, you typically don't. (consider posting on https://salesforce.stackexchange.com/, there might be a clever way I didn't think of).
You can flip the connected app from "all users can self authorise" to "admin-approved users are preauthorised" and then allow only certain profiles / permission sets to use the app. But the bulk of it is "just" enabling the connection via API and cutting it to say Chatter only or OpenId identifiers. And that's already an improvement compared to SOAP APIs where you don't have scopes and the app can completely impersonate the user, do everything they can do in UI.
Profiles/permission sets/sharing rules are "the" way even in not immediately obvious situations like Lighting Connect Salesforce to Salesforce or Named Credentials access to another org.
If you can't restrict the visibility with profiles and access to all tables user can see is not acceptable...
with sharing, WITH SECURITY_ENFORCED, stripInaccessible
+ custom restriction on tables before returning results