What's the connection between the Laplace transform and the Fourier transform? Both the Laplace transform and the Fourier transform in some sense decode the "spectrum" of a function. The Laplace transform gives a power-series decomposition whereas the Fourier transform gives a harmonic (or loop-based) decomposition.

Are there deep connections between these two transforms? The formulaic connection is clear, but is there something deeper?

(Maybe the answer will involve spectral theory?)
I don't know what answer you are looking for but for example both Laplace and Fourier transform are a so called Gelfand Transform.

You can find good introduction to Gelfand Transform in nice book Functional analysis for probability and stochastic processes: an introduction, A. Bobrowski. Look into Chapter 6.
Fourier transform does not exist for every signal application.So by introducing the region of convergence in Fourier transform which is known as Laplace Transform one may have indirectly the Fourier transform of signal.