It's my understanding that selecting for small models, i.e. having a multi-objective function where you're optimizing for both model accuracy and simplicity, automatically takes care of the danger of overfitting the data.
Sort of. A secondary objective function often works as a form of regularisation, and can work to reduce overfit.
However, this regularisation is not a magic bullet. The degree of regularisation that you achieve will vary, it may depend on hyper-parameters in the regularisation technique. In your case the relative weightings of objective functions for the accuracy and simplicity of the model will have a sweet spot that minimises overfit without compromising too much and under-fitting instead.
It would be very convenient for my use case to be able to skip lengthy cross-validation procedures.
Typically using regularisation requires cross-validation in order to find good values for your regularisation hyperparameters. If the regularisation technique you have chosen is a good fit for your problem, then you may not have to search too much - there may be a broad set of values that work well for you.
In turn, a good choice of regularisation may mean that your model's accuracy is less sensitive to other hyperparameters of your model, so searching for an accurate model becomes a little easier.
Does adding a model complexity penalty to the loss function allow you to skip cross-validation?
No. Assuming you want to find the best performing model, you still have to perform cross-validation. At best you may have to perform a little less than without the added objective because it has stabilised your model against other factors that can affect generalisation. However, you might have to perform more cross-validation, at least initially, in order to establish useful values of the new relative weighting hyperparameters you added with the secondary objectives. In addition the new simplicity objective function will likely change the best choices for other hyperparameters, such as number of free parameters, learning rate and length of training time.
If you were previously performing cross-validation after every epoch of training and picking the best model after the epoch that gave the best accuracy on the cv set, then that is often considered a different form of regularisation called early stopping. You may find you could relax this and test less often during training, because with regularisation based on complexity objectives, the training will tend towards a more stable end point and be less likely to overfit through additional training epochs. Although in my experience cross-validation during training is usually left on by default, in order to plot learning curves and ensure this stability really holds.