General guidelines in making a choice between Combinational or Sequential approach?
You haven't mentioned clock rate or performance but these are the most critical determinants of the correct approach to use, along with resource usage.

There is no single answer; typically you would explore different tradeoffs and select a best fit from among them.

Typically, if you start with a purely combinational solution, you will end up with a fairly large circuit, operating fairly slowly, delivering an output in a single clock cycle with a fairly long clock period. The longest combinational path (normally the longest chain of gates) determines the clock speed.

You would normally add registers to its inputs and/or outputs, to synchronise all incoming and outgoing signals to a common clock (avoiding issues of race conditions and timing hazards)

Now if that meets your size and speed targets : job done. 

If not, explore tradeoffs to improve the failing aspects.

Reduce the resource usage

If the resource usage is too high, identify repetitive sub-operations, and serialise them, e.g. adding one bit at a time in a single bit adder. You now need n clock cycles (plus some overhead) to achieve an n-bit result. However the computation is not n times slower. To whatever extent you have shortened the combinational path, you can increase the clock speed to recover some of the lost time.

The combinational logic occupies 1/n of the area. However you need to stream one bit per cycle through it, i.e. storing your data in shift registers, and shifting one bit at a time out of them. This adds resources.

Get it right however, and intermediate results may only need one bit of storage, as they are passed on to other serial elements. Input and output registers were recommended anyway; they can be shift registers with parallel load capability adding very little to the design size.

This can be the smallest implementation of all. 

Good examples of this architecture can be found in the valve (vacuum tube) architectures of about 1950, where every gate was large, power hungry and expensive. It is entirely possible to recreate similar designs in FPGA and they are absurdly small for their performance.

Increase performance

If the design is too slow, it is usually possible to break the combinational paths by inserting pipeline registers. This adds area in the form of additional registers, but (by shortening the combinational path length) allows you to increase the clock speed.

Add (for example) three pipeline registers, breaking the path into 4 equal paths, and you can increase the clock rate by 4. Any particular result will take at least as long to generate, but there are 4 results "in the pipeline" being computed in parallel - by the same amount of combinational logic! A classic example of this approach is the Pentium 4

In some FPGA architectures, you get one register per group of gates "for free", so if the combinational version uses lots of gates and no registers, the pipelined version can be (in this example) 4* as fast for no additional area.

Note that if you have to pipeline one arm of an "If" statement for performance, you would have to add a pipeline register to the other arm, to "balance" the pipeline (get results out in the same clock cycle), regardless of the "if" condition.

This is only the briefest introduction to the choices facing you, but hopefully it gives you some ideas.