Hello,
In this case, there are three issues as I can see:
1) Allow users to choose categorized content directly from their profile pages using Access
Yes, you are right, WordPress user does not custom taxonomy, you can not related taxonomy "category" in user's profile page directly, so you might consider create a custom post type (member profile), each "member profile" post's author is different wordpress user, and register taxonomy category to post type "member profile", see our document:
https://toolset.com/documentation/user-guides/how-to-create-custom-searches-and-relationships-for-users/
How to Create Custom Searches and Relationships for Users
2) Let users save videos to favourites (playlists - possibly using the player functions for this).
Yes, you can setup many-to-many relationship (for example: "video-member-profile") between post types "video" and "member profile".
In a single "video", you can create a relationship form, use it to relate the video post with "member profile" belongs to current user.
https://toolset.com/documentation/post-relationships/how-to-build-front-end-forms-for-connecting-posts/
So in the single "member profile" post, you can create a post view, query "video" posts, and filter by:
post type relationship "video-member-profile"
https://toolset.com/documentation/post-relationships/how-to-display-related-posts-with-toolset/#displaying-many-related-items
3) Create an admin to users one-way internal message system using toolset (not sure how yet).
You can try these:
a) Create a custom post type "message"
b) Setup one-to-many relationship between post types "member profile" and "message",
c) Create a post form for creating "message" post:
https://toolset.com/documentation/post-relationships/selecting-parent-posts-using-forms-create-child-items/
with email notification settings
https://toolset.com/documentation/user-guides/automated-email-notifications-with-cred/
After admin user submit above post form, use filter hook "cred_notification_recipients" to trigger a custom PHP function:
https://toolset.com/documentation/programmer-reference/cred-api/#cred_notification_recipients
in this function get related "member profile" post
https://toolset.com/documentation/customizing-sites-using-php/post-relationships-api/#toolset_get_related_post
and send email to "member profile" post author's email address:
https://developer.wordpress.org/reference/functions/get_the_author_meta/