Yes, it is correct. What makes you think it might not be correct? It is a contraction. The full form would be "perhaps Tom will start looking for a better job." (Written. Formal). The contracted form is "perhaps Tom'll start looking for a better job." (Spoken. Informal).

Yes, it's perfectly correct. We often use 'will' for predictions and suppositions, particularly when there is a lack of certainty. This contrasts with other futures such as: the present simple for a schedule ( 'My visa expires in 2019') the present continuous for a fixed arrangement ( 'I'm taking my driving test tomorrow') the 'going to' future for a plan ('I'm going to try and lose some weight') or for a prediction when there is clear evidence of what's going to happen ( 'That vase is going to fall off the table'). But when you're simply saying what you think might happen in the future, the 'will' future is fine.

Yes, if you're saying it aloud, you can say "Perhaps Tom'll start looking for a better job." This is because when you're speaking quickly, your words tend to blend together. So "Tom'll" is the same as "Tom will". However, if you're writing it down in a formal setting (like in a book), you'd usually write "Tom will", for example "Perhaps Tom will start looking for a better job", simply because it looks better to the eyes. Hope this helps! :)