Replace period with colon after Chapter (and Section) in header using fancyhdr package

Question

I am using the book document class and I am using the fancyhdr package. In my header, I am using \leftmark on the even pages and \rightmark on the odd pages.

I would like \leftmark to display "Chapter 1: Chapter One" instead of "Chapter 1. Chapter One".

I would like \rightmark to display "Section 1: Section One" instead of "Section 1. Section One".

How can I do this? Here is my code. Thanks in advance.

\documentclass[a4paper,12pt,twoside]{book}

\usepackage{lipsum}

\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage{fancyhdr}

% Code for headers
\renewcommand{\headrulewidth}{2pt}
\pagestyle{fancy}
\fancyhf{}
\fancyhead[LE,RO]{\textbf{\thepage}}
\fancyhead[CE]{\nouppercase{\leftmark}}
\fancyhead[CO]{Section \nouppercase{\rightmark}}

% Code to add page number on the right side of the footer on the chapter start page. 
\fancypagestyle{plain}{
    \fancyhf{}
    \renewcommand{\headrulewidth}{0pt}
    \fancyfoot[R]{\textbf{\thepage}}
}

\begin{document}
\chapter{Chapter One}
\section{Section One}
\lipsum
\lipsum
\end{document}

Answer 1

You can redefine the mark by modifying relevant code from book.cls. For example:

\documentclass[a4paper,12pt,twoside]{book}% If you say a4paper, be sure to load geometry
% \usepackage{geometry}
\usepackage{lipsum}
\usepackage{fancyhdr}

% Code for headers
\renewcommand{\headrulewidth}{2pt}
\pagestyle{fancy}
\fancyhf{}
\fancyhead[LE,RO]{\textbf{\thepage}}
\fancyhead[CE]{\nouppercase{\leftmark}}
\fancyhead[CO]{Section \nouppercase{\rightmark}}

% Code to add page number on the right side of the footer on the chapter start page.
\fancypagestyle{plain}{
    \fancyhf{}
    \renewcommand{\headrulewidth}{0pt}
    \fancyfoot[R]{\textbf{\thepage}}
}
\makeatletter
\def\chaptermark#1{% from book.cls
      \markboth {\MakeUppercase{%
        \ifnum \c@secnumdepth >\m@ne
          \if@mainmatter
            \@chapapp\ \thechapter: \ %
          \fi
        \fi
        #1}}{}}
\def\sectionmark#1{%
    \markright {\MakeUppercase{%
      \ifnum \c@secnumdepth >\z@
        \thesection: \ %
      \fi
      #1}}}
\makeatother

\begin{document}
\chapter{Chapter One}
\section{Section One}
\lipsum
\lipsum
\end{document}

I'm not certain whether this is the best way to do it, however.