Use Cyrillic characters in the table of contents with \pdfbookmark

Your original problem is solved by avoiding Cyrillic in PDF bookmark names. The reason for this is that with inputenc UTF-8 characters are something more than just characters. Instead of

\pdfbookmark[0]{Бытие}{Бытие}

write

\pdfbookmark[0]{Бытие}{Genesis}

However, it is easier to use the higher level \addcontentsline command, which not only adds an entry to the PDF TOC, but also to the LaTeX's primary table of contents, should it be printed:

\addcontentsline{toc}{chapter}{Бытие}

If you are going to do much work in Russian, you can also consider using the XeTeX engine instead of the default pdfTeX. XeTeX supports Unicode natively and allows to load any TrueType or OpenType font. Since XeTeX doesn't rely on tricks to work with UTF-8 and rather processes Unicode-encoded text directly, it is also possible to use Cyrillic (or any other) characters in PDF bookmark names and control sequence names (compile with xelatex instead of pdflatex or latex; polyglossia is the XeLaTeX replacement for babel):

\documentclass{book}

\usepackage{polyglossia}
\usepackage{hyperref}

\setdefaultlanguage{russian}
\newfontfamily\russianfont[Ligatures=TeX]{CMU Serif}

\begin{document}

\chapter{Проверка}
\pdfbookmark{Ещё проверка}{Название закладки}

\end{document}

See also this, this and this question.

Finally, I should also note that using low-level formatting commands over and over is not a good style and will soon bite you. You should, perhaps after reading some LaTeX tutorials (try also this exceptionally good, if not a bit old, book in Russian), define commands with semantic names and use them. You may also want to look at the titlesec package.

For same purpose I load the hyperref package with the option unicode independantly of input encodings.