Añadiendo algunas cosas a las que ya te han dicho.
(1) Debes asegurarte de que tu programa EXE no utiliza package en runtime, es decir, todo el programa está en un único fichero (revisa las opciones de proyecto).
(2) Si usas Paradox, posiblemente estés utilizando BDE; Por lo tanto el BDE debes instalarlo en la máquina cliente.
(3) Seguramente en el BDE has creado un Alias para tu Base de Datos. Ese Alias deberás crearlo en la máquina donde instales.
Si quieres hacer una SETUP.EXE típico, puedes utilizar el InstallShield que te han comentado y que viene con Delphi o algun otro tipo Inno Setup. Te comento este segundo porque ya tiene pensado las dos cosas que necesitas hacer tú junto con instalar el EXE. Seguro que con InstallShield también se puede hacer sin complicaciones.
El SETUP.EXE normal lo puedes generar con cualquiera de estos programas. Éstos te generan la instalación estandard; Copiar tus ficheros, crear los iconos y demás; Los otros dos pasos deberás añadírselos tú a esa instalación.
Inno Setup
Como instalar el BDE con Inno Setup
Cómo crear el alias en el BDE (un poco más abajo en la página)
Aquí tienes el proceso paso a paso y en castellano