In this paper, we study $k$-regular and completely $k$-regular semirings. We characterize the minimal $k$-bi-ideals in $k$-regular semirings via principal $k$-bi-ideals and also in completely $k$-regular semirings via $k$-bi-ideals generated by $k$-idempotent elements. Finally we characterize the completely $k$-regular semirings by $k$-bi-ideals generated via $k$-idempotents.