Hiragana derive from kanji in cursive script. Formerly, for a certain syllable, people were using different kanji. Take for example the syllable "re": you could use a cursive version of 礼 or 連 as a "letter" that stands for this syllable.
You may want to read the linked wikipedia article about hentaigana toritobe provided.
Today, kana are standardized, and there is an official kana for each syllable. れ is from 礼. I would argue that it is not helpful to consider some of those glyphs from that image as kanji, otherwise you would have to say that the first line should be 己比寸連波. But only the standard kana are encoded in unicode/sjis, so 連 is used to represent that kana.
What may give problems as well is that it is not written in modern Japanese (the 古今和歌集 was written more than one millenium ago). There were no dokuten, so が would be written か&c., some sound changes have changed some words in modern Japanese, so you might not recognize them immediately.
Take the first line: こひすれは
Add dakuten: こひすれば
"h" inside words becomes silent: こいすれば
(except ha: かは->かわ->川)
Add some kanji: 恋 為れば
Finally, it also uses archaic grammar: 成りにけり. You can look up にけり in a dictionary: [過去・詠嘆の意を表す]…てしまった(のだなあ)。