Considering the shortcomings of known medical hemostatic materials such as bone wax for bleeding bone management, it is essential to develop alternative bone materials capable of efficient hemostasis and bone regeneration and adaptable to clinical surgical needs. Thus, in the current work, a calcium sulfate hemihydrate and starch-based composite paste was developed and optimized. Firstly, it was found that the use of hydroxypropyl distarch phosphate (HDP) coupled with pregelatinization could generate an injectable, malleable and self-hardening paste with impressive anti-collapse ability in a dynamic aqueous environment, suggesting its potential applicability in both open and minimally invasive clinical practice. The as-hardened matrix exhibited a compressive strength of up to 61.68 ± 5.13 MPa compared to calcium sulfate cement with a compressive strength of 15.16 ± 2.42 MPa, making it a promising candidate for the temporary mechanical stabilization of bone defects. Secondly, the as-prepared paste revealed superior hemostasis and bone regenerative capabilities compared to calcium sulfate cement and bone wax, with greatly enhanced bleeding management and bone healing outcomes when subjected to testing in in vitro and in vivo models. In summary, our results confirmed that calcium sulfate bone cement reinforced with the selected starch can act as a reliable platform for bleeding bone treatment, overcoming the limitations of traditional bone hemostatic agents.