Robin Chapman's answer is very apropos. Here is a theoretical answer that points out a subtlety in the question.
First, recall that the primitive recursive functions are the smallest class of functions on $\mathbb{N}$ that:
- Includes the constant zero function, the successor function, and all projection functions;
- is closed under composition;
- and is closed under primitive recursion.
Let's call this class of functions $\operatorname{PR}(\emptyset)$. For any set $A$ of number theoretic functions, we can define a more general class $\operatorname{PR}(A)$ as the smallest class of functions that satisfies the above properties and also includes every function in $A$.
If every function in $A$ is computable, then every function in $\operatorname{PR}(A)$ is computable. Moreover, if every function in $A$ is total then every function in $\operatorname{PR}(A)$ is total.
It would be trivial, assuming $A$ is finite (or, more generally just explicitly enumerated), to create a programming language such that every program in the language computes a function in $\operatorname{PA}(A)$ and every such function has a program in the language. The language simply has primitives for all the functions in $A$ and for the basic primitive recursive functions, along with operators for composition and primitive recursion.
Therefore, one answer to "I'm curious about how "much" we can compute with a formalism that guarantees halting." is "For any total computable function there is such a formalism" and more generally this is true for any effective sequence of total computable functions.
The main thing that such a system cannot have is a universal function, provided the system has some basic closure properties.