You were right the second time.
Should have is always followed by a past participle, one of the basic forms of verbs.
From http://www.ecenglish.com/learnenglish/lessons/should-have-past-participle :
We use should have + past participle to talk about things we regret.
I got really wet walking home last night, I should have taken an
The speaker did not take an umbrella when she went out last night so
she got wet. She regrets that she did not take her umbrella.
Regret (verb/noun) is to feel sorry about something that happened or
did not happen in the past.
I should have called you sooner.
You should have spoken to me before deciding.
The past participle of come is also come.
From http://www.usingenglish.com/reference/irregular-verbs/come.html :
Conjugation of 'To Come'
Base Form: Come
Past Simple: Came
Past Participle: Come
3rd Person Singular: Comes
Present Participle/Gerund: Coming