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