Semi-decidable problems with linear bound Take a semi-decidable problem and an algorithm that finds the positive answer in finite time. The run-time of the algorithm, restricted to inputs with a positive answer, cannot be bounded by a computable function. (Otherwise we’d know how long to wait for a positive answer. If the algorithm runs longer than that we know that the answer is no and the problem would be solvable.)

My question is now: Can such an algorithm still have a, say, a run-time bound linear (polynomial, constant,...) in the input size, but with an uncomputable constant? Or would that still allow me to decide the problem? Are there example?
For your sketched decision algorithm to work, it is sufficient that the run-time is majorized by a computable function. Every linear function $n \mapsto c\cdot n$ even for non-computable c is majorized by a computable function, viz., $n \mapsto \lceil c \rceil \cdot n$. Thus the answer to the question is no: a semi-decision procedure for an undecidable problem cannot have linear run-time (or a run-time majorized by any computable function.)