Do server scripts (automation scripts) have access to ComposeUI?

Can we do ComposeUI.navigateToRecordPage when using server scripts?

Not (yet). Workflows do support this via prompts, but server-scripts do not. We might add this later on, but for now it is not on our todo.

Something that you could do is implement the core logic as a server script (whatever intensive processing that should not be in the front-end), and then define a client-script which redirects after the request is processed.

IIRC, this is not well documented, so I could prepare a quick draft that would cover your case