A few solutions courtesy of HackerNews.

A shell script:

#!/usr/bin/env bash

javas=$(find . -regex '.*\.java$')
sed -i -E "$(printf 's/\\<(%s)\\>/Kt\\1/g;' $(grep -hrPo '\b(class|interface|record|enum) (?!Kt)(?!List\b)(?!Entry\b)\K[A-Z]\w+'))" $(echo $javas); 
perl-rename 's;\b(?!Kt)(\w+[.]java)$;Kt$1;' $(echo $javas)

This is a little overzealous, but rolling back some of the changes was quick and painless. Also, Arch Linux doesn't have perl-rename installed by default, so that's needed.

Another solution is to create a Kotlin IDEA plug-in:

1. Install, run, then import the project into IDEA.
2. Install the Kotlin plug-in for IDEA.
3. Press Ctrl+Shift+A to open the Script Engine menu.
4. Select Kotlin.
5. Paste the script (given below).
6. Press Ctrl+A to select the script.
7. Press Ctrl+Enter to integrate the script into the IDE.
8. Open the Project window.
9. Select a single package directory (i.e., a root-level package).
10. Click Navigate >> Search Everywhere.
11. Click the Actions tab.
12. Search for: Bulk
13. Select Bulk refactor.

The classes are renamed. Note: There may be prompts for shadowing class names and other trivial issues to resolve.

Script

@file:Suppress("NAME_SHADOWING")

  import com.intellij.notification.Notification
  import com.intellij.notification.NotificationType
  import com.intellij.notification.Notifications
  import com.intellij.openapi.actionSystem.*
  import com.intellij.openapi.keymap.KeymapManager
  import com.intellij.openapi.command.WriteCommandAction
  import com.intellij.psi.*
  import com.intellij.psi.search.*
  import com.intellij.refactoring.rename.RenameProcessor
  import com.intellij.util.ThrowableConsumer
  import java.io.PrintWriter
  import java.io.StringWriter
  import javax.swing.KeyStroke

  // Usage: In IDEA: Tools -> IDE Scripting Console -> Kotlin
  // Ctrl+A, Ctrl+Enter to run the script
  // Select folder containing target classes, Ctrl+Shift+A to open action menu, search for Bulk refactor

  //<editor-fold desc="Boilerplate">
  val b = bindings as Map<*, *>
  val IDE = b["IDE"] as com.intellij.ide.script.IDE

  fun registerAction(
    name: String,
    keyBind: String? = null,
    consumer: ThrowableConsumer<AnActionEvent, Throwable>
  ) {
    registerAction(name, keyBind, object : AnAction() {
      override fun actionPerformed(event: AnActionEvent) {
        try {
          consumer.consume(event);
        } catch (t: Throwable) {
          val sw = StringWriter()
          t.printStackTrace(PrintWriter(sw))
          log("Exception in action $name: $t\n\n\n$sw", NotificationType.ERROR)
          throw t
        }
      }
    });
  }

  fun registerAction(name: String, keyBind: String? = null, action: AnAction) {
    action.templatePresentation.text = name;
    action.templatePresentation.description = name;

    KeymapManager.getInstance().activeKeymap.removeAllActionShortcuts(name);
    ActionManager.getInstance().unregisterAction(name);
    ActionManager.getInstance().registerAction(name, action);

    if (keyBind != null) {
      KeymapManager.getInstance().activeKeymap.addShortcut(
        name,
        KeyboardShortcut(KeyStroke.getKeyStroke(keyBind), null)
      );
    }
  }

  fun log(msg: String, notificationType: NotificationType = NotificationType.INFORMATION) {
    log("Scripted Action", msg, notificationType)
  }

  fun log(
    title: String,
    msg: String,
    notificationType: NotificationType = NotificationType.INFORMATION
  ) {
    Notifications.Bus.notify(
      Notification(
        "scriptedAction",
        title,
        msg,
        notificationType
      )
    )
  }
  //</editor-fold>

  registerAction("Bulk refactor") lambda@{ event ->
    val project = event.project ?: return@lambda;
    val psiElement = event.getData(LangDataKeys.PSI_ELEMENT) ?: return@lambda

    log("Bulk refactor for: $psiElement")

    WriteCommandAction.writeCommandAction(event.project).withGlobalUndo().run<Throwable> {
      psiElement.accept(object : PsiRecursiveElementWalkingVisitor() {
        override fun visitElement(element: PsiElement) {
          super.visitElement(element);
          if (element !is PsiClass) {
            return
          }

          if(element.name?.startsWith("Renamed") == false) {
            log("Renaming $element")

            // arg4 = isSearchInComments
            // arg5 = isSearchTextOccurrences
            val processor = object : RenameProcessor(project, element, "Renamed" + element.name, false, false) {
              override fun isPreviewUsages(usages: Array<out UsageInfo>): Boolean {
                return false
              }
            }
  
            processor.run()
          }
        }
      })
    }
  }